【剑指offer】数组中只出现一次的数字-蒲公英云

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

题目描述

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

思路

首先这道题本可以直接对所出现的数进行计数，然后输出数组中只出现一次的两个数字。

但是题上特地说了一下其他数字都出现了两次，说明题意是想考察的是另一个知识点：

位运算中的异或运算：两个相同的数进行异或时，结果为0

因此如果我们从头到尾依次异或数组中的每一个数字，那么最终得到的结果就是两个只出现一次的数字的异或结果，

由于这两个数字不一样，那么这个异或结果肯定不为0 ，也就是说在这个结果数字的二进制表示中至少就有一位为1 ，

我们在结果二进制中保留最高位的1（假设为第N位），并将其它的都置为0，然后拿这个数与原数组进行与运算，

这样原数组就会被我们分为两个子数组，第一个子数组中每个数的第N 位都为1 ，而第二个子数组的每个数的第N 位都为0 。

现在我们已经把原数组分成了两个子数组，而只出现一次的两个数字也被我们分到了两个不同的子数组中，

因此再对两个子数组进行异或之后就可以得出最终的结果了，而且题上并没有说明要按顺序找出这两个数字，

那么到此为止，问题就被我们解决了。

代码

class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
        if(data.empty())
            return;
        int x = 0;//用于保存num1和num2的异或结果
        for(int i = 0; i < data.size(); i++)
            x ^= data[i];
        int t = 1;//保留x中第一个1的位置，其它都置为0
        while(x>>1){
            t *= 2;
            x = x>>1;
        }
        *num1 = *num2 = 0;
        for(int i = 0; i < data.size(); i++){
            if(t & data[i]){
                *num1 ^= data[i];
            }
            else
                *num2 ^= data[i];
        }
        return;
    }
};