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

首先肯定想的是暴力统计筛选，能过

#include<iostream>

#include<vector>

#include<algorithm>

  

class Solution {

public:

    /**

     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

     *

     *

     * @param nums int整型vector

     * @return int整型vector

     */

    vector<int> FindNumsAppearOnce(vector<int>& nums) {

        std::vector<int> count(1000000,0);

        std::vector<int> result;

        for(int i=0;i<nums.size();i++)

        {

            count[nums[i]]++;

        }

        for(int j=0;j<count.size();j++)

        {

            if(count[j]==1){result.push_back(j);}

        }

        std::sort(result.begin(),result.end());

        return result;

    }

};

但是只出现两次与只出现一次这个东西就非常凑巧，异或能正好把只出现一次的筛选出来，因此选择整体处理的思想

#include<iostream>
#include<vector>
#include<algorithm>

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型vector
     */
    vector<int> FindNumsAppearOnce(vector<int>& nums) {
        //整体处理思想：只出现一次--》整体异或会留下
        //两个数字（a,b）则留下a,b-->分离a,b
        //a,b不同处，即是整体异或中为1的那几位
        //小技巧：&+补码得到最右为1的位（diff）
        //利用diff位分离ab---》退化成一个数字只出现一次的问题---->整体异或求解
        int XORsum=0;
        for(int i:nums)
        {
            XORsum^=i;   //得到a^b
        }

        int diff=XORsum & -XORsum;
        int a=0,b=0;     //0初始化不影响异或
        for(int j:nums)
        {
            if((j&diff)!=0)
            {
                a^=j;
            }else b^=j;
        }
        std::vector<int> ans={a,b};
        std::sort(ans.begin(),ans.end());
        return ans;
       
    }
};

进一步思考：要是有三个及以上的数出现怎么办，XOR取巧的方法还适用吗。

个人感觉，该XOR取巧的关键是分离出a,b；而分离出a,b用的方法更为取巧，是&+补码保留最右的“1”

但是三个以上似乎没有像保留最右1这样的方法。因此我能想到的可能只能分治+递归去把问题化成许多只包含两个与一个的出现一次数的数组，那么难点就转移到了如何去合理分割。

本蒟蒻的瞎想，还请各佬随意批评指正。。。