如果没看过《剑指 offer》的话，我可能很难想到这道题可以这样解。
首先，如果要寻找一个只出现一次的数字，直接把数组中所有数字异或即可（时间复杂度为 O(n)），但是如果需要寻找两个，那就会麻烦很多。因为将所有数字异或之后，能得到的只是两个只出现一次数字相互异或的结果。
思路继续。一方面，这两个数字不同，所以异或的结果肯定不为 0，那么是不是可以找到两个数字不一样的位呢？是的，这两个数字异或结果的任何不为 0 的位都是两个数字不同的位。另一方面，我们如果可以将这一列数字分为两列，而这两个数字各在一列之中，那么这个问题是不是就可以解了。
所以，就能想到可以利用两个数字异或结果中为 1 位（比如从右往左数第一个不为 0 的位）来将该数列分为两列，因为首先这两个数字中的这一位一定不同，可以被这一位分为两列；第二，数列中其它不同的数字可能会被分到不同的两列中，而相同的数字会被分为同一列中（因为相同的数字所有位都相同）；第三，这两列数字刚好符合要求——各包含一个只出现一次的数字，剩下包含的都是出现了两次的数字。
最后，在代码中，我使用了掩码运算代替了书中重复的移位运算。
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
| class Solution {
public:
void FindNumsAppearOnce(vector<int> data,int* num1,int* num2) {
if(data.size()<2) return;
vector<int>::iterator it;
int mixed_num=0;
for(it=data.begin();it!=data.end();it++){
mixed_num^=*it;
}
int firstNonZero=this->getFirstNonZeroMask(mixed_num);
*num1=*num2=0;
for(it=data.begin();it!=data.end();it++){
if((*it&mixed_num)==0) *num1^=*it;
else *num2^=*it;
}
}
int getFirstNonZeroMask(int mixed_num){
int t=1;
while(t<mixed_num){
if((mixed_num&t)!=0) return t;
t<<=1;
}
return 0;
}
};
|