数组中只出现一次的数字

写在前面

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

题目要求

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

解法

解法1：使用一个map记录每个值出现的次数，最后遍历一遍map得到只出现一次的值。时间复杂度o(n),空间复杂度o(n)

class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
        if(data.size()<2) return;
        unordered_map<int,int> table;
        for(int i=0;i<data.size();++i) {
            ++table[data[i]];
        }
        int tag = 0;

        for(auto each:table) {
            if(each.second==1&&tag==0) {
                *num1 = each.first;
                ++tag;
            }
            else if(each.second==1&&tag==1)
                *num2 = each.first;
        }
    }
};

解法2：利用题目的特性重复出现的值都是偶数次，所以将所有的元素异或，所有重复出现的值异或的结果将相互抵消最终得到的值是两个单独出现的值的异或结果。找到结果当中第一个为1的位，以该位将所有的元素分成两组，由于在这一位上这两个数是不同的所以这两个数将在不同的组当中，并且其他的重复元素也不会出现分散在两组的可能。再次对两组求异或得到两个值。

class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
        if(data.size()<2) return;
        int temp = 0;
        for(int i=0;i<data.size();++i) {
            temp ^= data[i];
        }
        if(temp==0) return;
        int x = temp,count = 0;
        while((x&1)==0) {
            x = (x>>1);
            ++count;
        }
        int t = 0;
        x = (1<<count);
        for(int i=0;i<data.size();++i) {
            if((data[i]&x)>0)//这里>的优先级高于&所以必须加上括号
                t ^= data[i];
        }
        *num1 = t;
        *num2 = temp^t;
    }
};