【剑指offer】数组中只出现一次的数字

数组中只出现一次的数字

题目描述

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

思路

我们知道两个相同的数字异或的结果为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;
}