题目

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

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {

        if(data.size()<2) return;
        int myxor=0;
        int flag=1;
        for(int i=0;i<data.size();i++)
        {
            myxor =myxor^data[i];
        }
        while((myxor & flag) == 0) flag <<= 1;
        for(int i = 0; i < data.size(); ++ i ){
            if((flag & data[i]) == 0) *num2 ^= data[i];
            else *num1 ^= data[i];
        }
        return;
    }
};

思路

经典的位运算题目。首先把所有数字异或起来，两个相同的数字异或等于0，所以最终的结果是两个只有一个的数字异或得到的结果。然后，不断的移位找到第一个为1的位置（在这个位置上，两个只有1个的数是不相同的），然后重新遍历数组根据这一位来遍历，分成两个数组，然后每个数组之间异或，得到的就是两个数字。