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

一.题目描述
Nc75数组中只出现一次的两个数字
题目链接:
https://www.nowcoder.com/practice/389fc1c3d3be4479a154f63f495abff8?tpId=188&&tqId=38602&rp=1&ru=/activity/oj&qru=/ta/job-code-high-week/question-ranking
一个整型数组里除了两个数字只出现一次，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
二.算法(暴力模拟)
要找到数组中只出现一次的两个数字，最容易想到的就是对整个数组进行遍历，然后找出两个只出现一次的数字。
利用c++sTL中的map可以很好的解决这个问题，下面是完整代码:

class Solution {
public:
    vector<int> FindNumsAppearOnce(vector<int>& array) {
        map<int,int>mp;
        for(int i=0;i<array.size();i++){
            mp[array[i]]++;
        }
        vector<int>q;//返回最后的两个数字
        for(auto &i:mp){
            if(i.second==1){
                q.push_back(i.first);/要是只出现一次 那就入队
            }
        }
        sort(q.begin(),q.end());//对返回的数组进行排序
        return q;
    }
};

时间复杂度：o(n)
空间复杂度：o(n*n)需要额外开辟空间返回结果和记录出现次数
优缺点：时间复杂度高，但是便于实现。

三.算法(位运算)

如上面例子中的数组，我们每做一次异或运算，最后的1会被消去，只剩下4和6的异或结果xor。
然后我们再找这个xor的最后一个1的位置:xor-xor&(xor-1)
因为根据题目要求有两个数是不重复的，所以最后一个1的位置说明这两个数在这个位置上的二进制的数字是不同的，我们可以根据这个特性给它们分别存放在容量为2的数组的不同的位置中。得到最后的1这个数字之后，用这个数再次与整个数组进行异或运算，重复的数会被消去，只剩下那个唯一的值就是结果。下面给出完整代码:

class Solution {
public:

    vector<int> FindNumsAppearOnce(vector<int>& array) {
        int x=array[0];
        for(int i=1;i<array.size();i++){
            x^=array[i];
        }
        //找到二进制中最右边的1
        x-=x&(x-1);
        vector<int>q;
        //提前放入两个数据 防止段错误
        q.push_back(0);
        q.push_back(0);
        for(int i=0;i<array.size();i++){
            //根据他们是1还是0 来分配在数组q中的位置
            if((x&array[i])==0) q[0]^=array[i];
            else q[1]^=array[i];
        }
        //排序
        sort(q.begin(),q.end());
        return q;
    }
};

时间复杂度:o(n)
空间复杂度:o(n) 需要额外空间来存在返回结果
优缺点:空间利用率低，但是实现起来复杂