问个算法方面的问题

V2EX = way to explore

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

现在注册

已注册用户请登录

V2EX 提问指南

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

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

一百万个

无规律

一百万

22 条回复 • 2014-05-17 00:16:15 +08:00

skydiver

2014-05-15 20:11:07 +08:00

异或

dennisyang

2014-05-15 20:25:24 +08:00

分块hash？

john990

2014-05-15 20:35:31 +08:00

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

skydiver

2014-05-15 20:41:07 +08:00

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

john990

2014-05-15 20:59:26 +08:00

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

skydiver

2014-05-15 21:21:48 +08:00

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

bengol

2014-05-15 21:26:00 +08:00

为什么会多了一个？

john990

2014-05-15 21:34:40 +08:00

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

YouXia

2014-05-15 21:37:02 +08:00

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

txx

2014-05-15 21:47:47 +08:00

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

jsonline

2014-05-16 00:05:39 +08:00

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

wy315700

2014-05-16 00:16:47 +08:00

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

stevenyou

2014-05-16 09:31:01 +08:00

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

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

stevenyou

2014-05-16 09:31:51 +08:00

效率是O(n)

john990

2014-05-16 09:49:35 +08:00

@stevenyou 嗯，好办法

cassyfar

2014-05-16 10:29:58 +08:00

@stevenyou 有overflow的风险
@john990

stevenyou

2014-05-16 10:55:40 +08:00

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

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

stevenyou

2014-05-16 10:56:32 +08:00

@cassyfar sorry , 16bit int

cassyfar

2014-05-16 12:30:36 +08:00

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

riaqn

2014-05-16 12:39:37 +08:00

@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

2014-05-16 12:53:55 +08:00

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

Virtao

2014-05-17 00:16:15 +08:00

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

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

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