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

V2EX = way to explore

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

现在注册

已注册用户请登录

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

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 月 5 日

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 月 5 日 via Android

这么低？怎么低？

iEverX

2015 年 11 月 5 日

这是最快了吧？

firemiles

2015 年 11 月 5 日

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

MntCw

2015 年 11 月 5 日

int ret = nums[0]

sleeperqp

2015 年 11 月 5 日

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

firemiles

2015 年 11 月 5 日

@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 月 5 日

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