问个算法方面的问题

This topic created in 4559 days ago, the information mentioned may be changed or developed.

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

一百万个

无规律

一百万

22 replies • 2014-05-17 00:16:15 +08:00

skydiver

May 15, 2014

异或

dennisyang

May 15, 2014

分块hash？

john990

May 15, 2014

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

skydiver

May 15, 2014

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

john990

May 15, 2014

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

skydiver

May 15, 2014

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

bengol

May 15, 2014

为什么会多了一个？

john990

May 15, 2014

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

YouXia

May 15, 2014

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

txx

May 15, 2014

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

jsonline

May 16, 2014

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

wy315700

May 16, 2014

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

stevenyou

May 16, 2014

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

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

stevenyou

May 16, 2014

效率是O(n)

john990

May 16, 2014

@stevenyou 嗯，好办法

cassyfar

May 16, 2014

@stevenyou 有overflow的风险
@john990

stevenyou

May 16, 2014

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

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

stevenyou

May 16, 2014

@cassyfar sorry , 16bit int

cassyfar

May 16, 2014

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

riaqn

May 16, 2014

@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

cassyfar

May 16, 2014

@stevenyou 确实没影响只要差值保留住就可以了和overflow多少次无关

Virtao

May 17, 2014

之前V2EX上就有个类似的题目，再次分享我的总结：

http://blog.virtao.org/articles/163.html

另外严重同意 @skydiver 的说法，这类题目玩玩可以，当面试题没意义。万一碰到个大牛恰好这个题目没碰到过呢？