算法 异或

原贴的地址在这里 一道腾讯算法题引出的思考, 因为没有地方给他留言这个解法, 所以我就直接水一篇博客吧.

题目

题目的大意是这样的:

目前有一万零一个数(无序), 范围是1~10000, 除了有两个重复数字之外, 其它数字都不重复, 怎么最快找出这两个重复数字?

简单分析一下, 1~10000 一共是10000个数字, 那么再多出来的一个数字就是我们要找的发生了重复的数字.

以下面这个数组为例, 最后的23就是我们想得到的.

1
[1, 2, 3, 4, ..., 10000, 23]

当然上面的例子很简单, 一眼就能看出了答案, 乱序的数组就不是很容易看的出来了.

如何求解.

乱序的数组确实不好判断, 那我们还是以上面这种特殊的顺序来看,

请大家试着将数组的下标标记出来, 类似这样一张表
数组的值 1 2 3 4 5 ….. 10000 23
数组下标 0 1 2 3 4 …. 9999 10000

大家有没有发现, 数组下标和原数组的值, 合并起来, 像什么呢

1
0, 1, 1, 2, 2, 3, 3, 4, 4 ...  10000, 10000, 23

这个问题就转换成了, 在1~10000中, 所有的数字出现了2次(抛去0), 有个数字出现了3次, 然后我们要找到这个数字, 祭出我们的异或法就可以了.

上面的数组是按顺序排的, 即使是乱序的数组, 也总是可以重新排列来得到这样的关系.

下面是我的求解方法, 为了简便直接用Python写了

1
2
3
4
5
6
7
8
9
10
11
import random
x = list(range(1, 10001))  # 1 ~ 10000的数组
x.append(238)  # 随便给定要求的数字
random.shuffle(x)  # 打乱整个数组

rlt = 0
for idx, num in enumerate(x):
    rlt = rlt ^ idx ^ num  # 针对数组元素与下标进行连续的异或操作

print(rlt)
# 肯定可以获得238的

时间空间复杂度分析

因为问题中给定了是10001个数字, 这样算下来时间复杂度应该是O(10000), 空间复杂度就是O(1)了.

没法留言确实太烦人了, 希望大家的博客也能添加个留言板, 也好交流啊.