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

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

分析

我们先来看一道问题：

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

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

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

代码如下：

```int FindFirstBitIs1(int num) { 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& 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上：点我前往