一个整型数组里除了两个数字之外，其他的数字都出现了两次

果子

请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

1. #include<iostream>
2. using namespace std;
3. int findFirstOne(int value);
4. bool testBit(int value,int pos);
6. int findNums(int array[],int length,int &num1,int &num2){
9.     if(length<2){return -1;}
10.     int ansXor=0;
11.     for(int i=0;i<length;i++)
12.     {
13.         ansXor^=array[i];               //异或
14.     }
16.     int pos=findFirstOne(ansXor);
17.     num1=num2=0;
18.     for(int i=0;i<length;i++)
19.     {
20.         if(testBit(array[i],pos))
21.             num1^=array[i];
22.         else
23.             num2^=array[i];
24.     }
25.     return 0;
26. }
29. int findFirstOne(int value)
30. {     //取二进制中首个为1的位置
31.     int pos=1;
32.     while((value&1)!=1)
33.     {
34.         value=value>>1;
35.         pos++;
36.     }
37.     return pos;
38. }
41. bool testBit(int value,int pos)
42. {  //测试某位置是否为1
43.     return ((value>>pos)&1);
44. }
46. int main(void)
47. {
48.     int array[10]={1,2,3,4,5,6,4,3,2,1};
49.     int num1,num2;
51.     if(findNums(array,10,num1,num2)==0)
52.         cout<<num1<<" "<<num2<<endl;
53.     else
54.         cout<<"error"<<endl;
56.     return 0;
57. }

复制代码

1、首先第一次遍历整个数组，找出不同的那两个数的异或后的结果,见下面这段代码.

1. for(int i=0;i<length;i++)
2. {
3.         ansXor^=date[i];               //异或
5.     }

复制代码

2、找到异或结果中ansXor中用移位的方式找到第一个二进制数中为1的位置，这个很关键，找到这个位置后，说明在该位置上，这两个不同的数中，一个为0，一个为1，这个应该可以理解对吧？

1. int pos=findFirstOne(ansXor);

复制代码

我们把这个位置记为pos

3、然后再遍历一次数组，把这个数组分成两个子数组，pos位上为1的，和pos位上为0的

1. for(int i=0;i<length;i++)
2. {
3.         if(testBit(date[i],pos))
4.            num1^=date[i];
5.        else
6.             num2^=date[i];
7. }

复制代码

这里借助了异或的原理，pos位置上为1的其它成双成对的数肯定也是为1的，同理，pos位上为0的时也一样。