Niuke: two numbers that only appear once in the array

Catalog

Method 1 ： Hashtable

Method 2 ： Exclusive or operation

---

Method 1 ： Hashtable

Set up a hash table to store < Numbers , Number of occurrences > Hash table for , Search times and sorting after

class Solution {
public:
    /**
     *  The class name in the code 、 Method name 、 The parameter name has been specified , Do not modify , Return the value specified by the method directly 
     *
     * 
     * @param array int integer vector 
     * @return int integer vector
     */
    vector<int> FindNumsAppearOnce(vector<int>& array) {
        // write code here
        unordered_map<int, int> mp;
        vector<int> res;
        for(int i=0;i<array.size();++i){
            mp[array[i]]++;
        }
        for(int i=0;i<array.size();++i){
            if(mp[array[i]]==1){
                res.push_back(array[i]);
            }
        }
        if(res[0]>res[1]){
            swap(res[0], res[1]);
        }
        return res;
    }
};

Method 2 ： Exclusive or operation

It's a very clever idea ：

Let's first find the XOR of all numbers , This will result in the XOR of two answer numbers . Then we find the first one for this result 1.

This position is very clever , The two answer numbers are different in this position , Other numbers will appear twice in this position , And then do XOR operation to offset .

The code is as follows ：

class Solution {
public:
    /**
     *  The class name in the code 、 Method name 、 The parameter name has been specified , Do not modify , Return the value specified by the method directly 
     *
     * 
     * @param array int integer vector 
     * @return int integer vector
     */
    vector<int> FindNumsAppearOnce(vector<int>& array) {
        // write code here
        vector<int> res(2,0);
        int temp=0;
        for(int i=0;i<array.size();++i){
            temp^=array[i];
        }
        int k=1;
        while((k&temp)==0){
            k<<=1;
        }
        for(int i=0;i<array.size();++i){
            if((k&array[i])==0){
                res[0]^=array[i];
            }else{
                res[1]^=array[i];
            }
        }
        if(res[0]>res[1]){
            swap(res[0], res[1]);
        }
        return res;
    }
};