Leetcode 上一道简单题的效率问题

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

V2EX 提问指南

这是一个创建于 3343 天前的主题，其中的信息可能已经有所发展或是发生改变。

Single Number

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Subscribe to see which companies asked this question

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret = 0;
         for(int i:nums) {
             ret ^= i;
         }
         return ret;
    }
};

上 leetcode 做了一道题，怎么也想不明白为什么这个写法效率这么低，效率最高的那部分代码要怎么写才能达到？

第 1 条附言 · 2015-11-05 15:35:46 +08:00

https://www.evernote.com/shard/s159/sh/451cbc15-debd-4401-ae16-c2303676e093/d7b6d7925925e231e2e6af90255b1c73
这个是效率排名

7 条回复 • 2015-11-05 22:03:53 +08:00

msg7086

2015-11-05 14:41:06 +08:00 via Android

这么低？怎么低？

iEverX

2015-11-05 15:00:48 +08:00

这是最快了吧？

firemiles

2015-11-05 15:37:23 +08:00

@iEverX
@msg7086
https://www.evernote.com/shard/s159/sh/451cbc15-debd-4401-ae16-c2303676e093/d7b6d7925925e231e2e6af90255b1c73
上面是排名数据

MntCw

2015-11-05 15:40:26 +08:00

int ret = nums[0]

sleeperqp

2015-11-05 15:53:14 +08:00

额你用你代码重新提交一下试试 ╭(╯^╰)╮ 有可能是 20ms 这种东西不要深究

firemiles

2015-11-05 17:20:56 +08:00

@sleeperqp
```cpp
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ret = nums[0];
int len = nums.size();
for(int i=1; i<len; ++i) {
ret ^= nums[i];
}
return ret;
}
};
```
反复提交后终于到了第一梯队，看来还是 leetcode 的测试案例太少，运行时间太少导致排名不稳定

sleeperqp

2015-11-05 22:03:53 +08:00

@firemiles 也不一定这个还可能跟运行时服务器的运行负载有关 0 0
所以这个大概知道怎么做就最好了除非有很大的运行时间差距