题解 | #数组中只出现一次的两个数字#

题意思路：
一个整型数组里除了两个数字只出现一次，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

方法一：hash

将数组中所有元素遍历并映射到hash中统计数量，可以使用map保存数字和出现次数。

如果出现次数超过一次则删除数字

最后统计数组中只出现一次的两个数字。

复杂度分析

时间复杂度：O(NlogN)，N数组的长度，遍历数组，map插入删除时间复杂度为logN；

空间复杂度：O(N)，数组存储与读取数据。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector 
     * @return int整型vector
     */
    vector<int> FindNumsAppearOnce(vector<int>& array) {
        // write code here
        map<int, int>mp;//使用map映射保存数字和出现次数
        vector<int> res;
        for(int i:array){//遍历数组
            if(mp[i])mp.erase(i);//如果出现次数超过一次则删除数字
            else mp[i]++;
        }
        for(auto i:mp)res.push_back(i.first);//最后统计数组中只出现一次的两个数字
        return res;
    }
};

方法二：位运算 异或

按位异或的4个特点：
（0） 只有在两个比较的位不同时其结果是1，否则结果为0

　　（1） 0^0=0，0^1=1 0异或任何数＝任何数

　　（2） 1^0=1，1^1=0 1异或任何数=任何数取反

　　（3） 任何数异或自己＝把自己置0

题意表示除了出现一次的两个数字，其它数字都出现了两次，

根据特点三可以使相同数字异或为0，

然后0再异或出现一次的数字得到这个出现一次的数

但是异或所有数组元素后最后得到的异或结果是这两个只出现一次的异或结果

为了分别得到这两个数字，再次利用异或的性质0

从异或结果里面找一位1,因为某一位上异或结果是1的话，说明要找两个数，一个数这位是1，另一个是0。这一位是1的分成一组，这一位是0的分成一组，最后进行组内异或，这样得到两个数就是原来的数字

图解：

复杂度分析

时间复杂度：O(N)，N数组的长度，遍历数组，异或的时间复杂度为O(1)；

空间复杂度：O(1)，res数组只存了两个数

代码：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector 
     * @return int整型vector
     */
    vector<int> FindNumsAppearOnce(vector<int>& array) {
        // write code here
        vector<int>res;
        int xorSum=0,a=0,b=0;
        for(int i:array){//遍历数组元素得到两个数的异或结果
            xorSum^=i;
        }
        int t=1;
        while((xorSum&t)==0){//找到异或结果中二进制位为1的数字
            t=t<<1;
        }
        for(int i:array){
            if(t&i){//根据异或性质 相同为0，不同为1 分别反推出两个数的结果
                a^=i;
            }
            else b^=i;
        }
        res.push_back(min(a, b));
        res.push_back(max(a,b));
        return res;
    }

};