数组中只出现一次的数字

题目描述

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

思路

我们知道两个相同的数字异或的结果为0，所以如果只有一个出现一次的数字，就可以让所有的数字进行异或，那么最后得到的数字就是只出现一次的数字。

现在问题变成了有两个数字，同样我们可以让所有数字异或，最终的结果是两个只出现一次的数字的异或的结果。我们可以找到这个结果的二进制位上为1的下标，例如异或的结果为4，那么对应到二进制上是100，所以在第三位上着两个数字不相同，一个为1，一个为0，所以我们可以以二进制中第三位为区分标准，把数组划分成两份，二进制的第三位为1和为0。

当得到两个小组后，我们知道这两个只出现一次的数已经被分开了，这样就回到最原始的问题上了，问题迎刃而解。代码如下。

代码

#include <iostream> 
#include <vector> 
using namespace std; 
 
void FindNumsAppearOnce(vector<int> data,int num1,int num2); 
int FindFirstOneBit(int target); 
bool isOneBit(int target, int index); 
 
void FindNumsAppearOnce(vector<int> data,int num1,int num2) { 
    if (data.size() < 2) 
        return; 
    int res = data[0]; 
    for(int i=1;i<data.size();i++) 
        res ^= data[i]; 
    int first = FindFirstOneBit(res); 
    num1 = num2 = 0; 
    for (int i = 0; i < data.size(); ++i) { 
        if(isOneBit(data[i], first-1)) 
            num1 ^= data[i]; 
        else 
            num2 ^= data[i]; 
    } 
 
    cout << num1<<endl; 
    cout<<num2 <<endl; 
} 
 
int FindFirstOneBit(int target) { 
    int ret = 0; 
    while((target ^ 1) == 0 && ret < 8* sizeof(int)) { 
        target = target >> 1; 
        ret++; 
    } 
    return ret; 
} 
 
bool isOneBit(int target, int index) { 
    target = target >> index; 
    return target & 1; 
} 
 
 
int main() { 
 
    vector<int> data = {1,1,2,2,3,4,3,5}; 
    FindNumsAppearOnce(data, 0, 0); 
    return 0; 
} 

结果

5

4