面试题40:数组中只出现一次的数字

题目:一个整型数组中除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个数字。要求时间复杂度是O(n),空间复杂度是O(1)。


分析

我们先来看一道问题:

一个整型数组中除了一个数字出现了一次之外,其他的数字都出现了两次。请找出这个数字。

这题怎么做呢?记得我们原来有一个模拟面试,当时面试老师就给我出了这么一道题目。我当时冥思苦想绞尽脑汁花了十几分钟写出来,结果老师看都没看,问我:你想两个相同的数字有什么特征?我立马就想起来了。因为两个相同的数字的异或结果为0!有了这个思路,结果我只花了几分钟的时间,用了原来四分之一的代码量就写出来了,确实简洁啊!

所以这道题也可以用相同的方法,将数组中的所有值异或过去,最后的结果肯定为两个只出现一次的数字的异或值!并且这给值肯定不为0.也就是至少有一位为1,这两个数的这一bit位肯定不相同。所以我们可以按照这一位是否为1将数组中的值分为两堆,对这两堆值分别求异或,最后的两个结果就是我们要找的数字。

代码如下:

FindFirstBitIs1(int num)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
{
int i,index=1;
for(i=0;i<8*sizeof(int);++i)
{
if((num & (index<<i)) ==0)
continue;
else
break;
}
return i;
}
bool IsBit1(int num,int pos)
{
return num&(1<<pos);
}
void FindNumbersAppearOnce(const vector<int>& v,int& n1,int& n2)
{
int i,res=0;
for(i=0;i<v.size();++i)
{
res^=v[i];
}
int n=FindFirstBitIs1(res);
n1=n2=0;
for(i=0;i<v.size();++i)
{
if(IsBit1(v[i],n))
{
n1^=v[i];
}
else
{
n2^=v[i];
}
}
}

以上

如果你有任何想法或是可以改进的地方,欢迎和我交流!

完整代码及测试用例在github上:点我前往

<div>来自为知笔记(Wiz)</div>