剑指offer40数组中只出现一次的两个数字

剑指offer40

1、常规方法--哈希、排序统计等
2、位运算
题解：数组所有数字异或，最终结果是要找的两个数字异或的结果，比如异或最后结果为X=0101，说明要找的两个数字a,b异或结果为0101，则a的第一位为1，b的第一位为0，即a = ###1 , b = ###0。通过这个结果，即按照第一位为1和0将数组分为两类，这样每一类中都包含若干对元素以及单独的一个a或者b,题目转化为---数组中寻找出现一次的数字，只有一个出现一次，其他出现两次。这种用位运算异或可以轻松解决
时间复杂度：O(n)
空间复杂度：O(1)
[1]:https://www.nowcoder.com/profile/396966893/codeBookDetail?submissionId=110360014
[个人代码][1]

//位运算
    //数组所有数字异或，最终结果是要找的两个数字异或的结果，比如异或最后结果为X=0101
    //说明要找的两个数字a,b异或结果为0101，则a的第一位为1，b的第一位为0，即a=***1,b=***0
    //通过这个结果，即按照第一位为1和0将数组分为两类，这样每一类中都包含若干对元素以及单独的
    //一个a或者b,题目转化为---数组中寻找出现一次的数字，只有一个出现一次，其他出现两次
    //这种用位运算异或可以轻松解决
    vector<int> FindNumsAppearOnce(vector<int>& array) {
        int ret=0; //所有元素异或结果
        for(int x:array) //所有数字异或 ret
            ret^=x;
        int mask=ret-(ret&(ret-1)); //mask为ret第一个1的位置 因为ret&ret-1消除ret的第一个1
        int index=0; //以index为界，index前面mask位是1，index后面(包括index)mask位置是0
        for(int i=0;i<array.size();i++)
        {
            if((array[i]&mask)!=0)
                swap(array[i],array[index++]);
        }
        int a=0;
        for(int i=0;i<index;i++)
        {
            a^=array[i];
        }
        int b=ret^a; //求出a后可以直接求b
        if(a<b)
            return {a,b};
        else
            return {b,a};
    }

或者如下处理也可

链接