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

时间:2022-06-06 13:11:57

数组中只出现一次的数字

题目描述

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

思路

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