问个算法方面的问题

[john990]

现有一百万个数（无规律，可重复），把这些数复制一份，发现多了一个（一百万零一个），怎么用最快的方法找到多了什么数？

[skydiver]

异或

[dennisyang]

分块hash？

[john990]

@skydiver 能详细点吗？
@dennisyang 这个是今天的面试题，我也是这么说的，面试的人说有更简单的。

[skydiver]

@john990 所有的数字异或到一起。重复的数字异或到一起就变成0了，剩下的就是多出来的数。
这是一个经典的面试题啊。。

[john990]

@skydiver oh，明白了，谢谢了，看来算法是硬伤啊

[skydiver]

@john990 这个题基本也考不了什么能力，知道就是知道，不知道就是不知道……拿这个题考人的公司感觉不怎么靠谱……

[bengol]

为什么会多了一个？

[john990]

@bengol x^x=0，x^0=x ；那两百万个数中任意一个数都是偶数个，所以异或到最后就剩下多出来的那个

[YouXia]

@skydiver 基本上G，M等家都问这种数学类型的题目。

[txx]

http://oj.leetcode.com/problems/single-number/ 常見題目

[jsonline]

对啊，为什么会多一个，搞清楚这个问题价值会更大吧。

[wy315700]

把所有的数异或一下 最后的结果就是那个多出来的数
简单的面试题

[stevenyou]

sum(一百万零一个) - sum(一百万个数)

得到的结果就是多的那一个

[stevenyou]

效率是O(n)

[john990]

@stevenyou 嗯，好办法

[cassyfar]

@stevenyou 有overflow的风险
@john990

[stevenyou]

@cassyfar 是有overflow的问题，但是从两个数可以看出来的。如果是32bit int
sum(一百万零一个) = -32768
sum(一百万个数) = 32767
可以知道多出的那个数是1

当然了，xor的方法是最好的。

[stevenyou]

@cassyfar sorry , 16bit int

[cassyfar]

@stevenyou 对啊 但是如果overflow之后又overflow就麻烦了 毕竟100万个数的和是个很大的和

[riaqn]

@cassyfar
@stevenyou
实际上 overflow 没有影响，2's complement 表示的整数是个阿贝尔群。
以下代码在 32bit 上运行， sizeof(int)=4

➜ ~ cat test.c
#include <stdio.h>
int main() {
int a = 1234567890;
int b = 2134567890;
printf("%d\n", a + b);
printf("%d\n", a + b - a);
}
➜ ~ gcc -o test test.c
➜ ~ ./test
-925831516
2134567890