题目描述

一个整型数组里除了两个数字之外，其他的数字都出现了两次。

请写程序找出这两个只出现一次的数字。

你可以假设这两个数字一定存在。

样例

输入：[1,2,3,3,4,4]

输出：[1,2]

算法

基础题是检测数组中只出现一次的一个数字,利用异或的结合律和交换律,a^a=0,0^a=a 的三个性质
所有元素异或则是只出现一次的数字
这里同样是把所有元素异或,而指出现一次的两个数字,变成二进制数,至少会有一位进制位不同
然后进行异或后,一定会得到1,可以以这个1为分界线,将数组分成两堆,每堆的处理就跟基础题一样了
而这里只需要进行一堆的基础题类似处理,因为之间存在转化关系

C++ 代码

class Solution {
public:
    vector<int> findNumsAppearOnce(vector<int>& nums) {
        int s=0;    //a^b
        int s1=0;   //a   b=a^b^a
        int pos=1;  
        for(int i=0;i<nums.size();i++)
        {
            s^=nums[i];
        }
        while(!(s>>pos&1))
            pos++;
        for(int i=0;i<nums.size();i++)
        {
            if((nums[i]>>pos)&1)
            {
                s1^=nums[i];    
            }
        }
        return vector<int>{s1,s^s1};
    }
};