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

#include <unordered_map>
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型vector
     */
    vector<int> FindNumsAppearOnce(vector<int>& nums) {
        // write code here
        unordered_map<int, int> ump;
        vector<int> ans;
        if(nums.empty()) return ans;
        for(int i = 0; i < nums.size(); ++i){
            ++ump[nums[i]];
        }
        for(int i = 0; i < nums.size(); ++i){
            if(ump[nums[i]]==1){
                ans.push_back(nums[i]);
            }
        }
        if(ans[0]>ans[1]){
            swap(ans[0], ans[1]);
        }
        return ans;
    }
};

用hash表，遍历一次记录出现次数，然后再遍历一次找到只出现一次的。

#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型vector
     * @return int整型vector
     */
    vector<int> FindNumsAppearOnce(vector<int>& nums) {
        // write code here
        vector<int> res(2, 0);
        if (nums.empty()) return res;
        int compare = 0;
        for (int i = 0; i < nums.size(); ++i) {
            compare ^= nums[i];
        }
        int checkOne = 1;
        while ((compare & checkOne) == 0)    checkOne <<= 1; //异或导致的，记得写等于号
        // res.push_back(0), res.push_back(0);
        for (int i = 0; i < nums.size(); ++i) {
            if ((checkOne & nums[i]) == 0)    res[0] ^= nums[i];
            else    res[1] ^= nums[i];
        }
        if(res[0]<=res[1]) return res;
        else    return {res[1], res[0]};
    }
};

异或能将相同的给抵消，不同的留下。（目的是找到不同的两个的分组依据）

这样一次后相当于要找的两个值异或。

找到1的位置就找到了两个值不同的位。

然后通过这个位去区分这组值，把它们分成两个组，因为这个位一样的一定在一个组，所以能继续相同的抵消。

最后两个组都再次异或（代码中与上一步结合在了一起），分别得到一个我们要求的。

然后排序，输出。