在做题中学习（36）：消失的两个数字

面试题 17.19. 消失的两个数字 - 力扣（LeetCode）

思路：丢失的数字 + 只出现一次的数字III

ps: 下面讲 丢失的数字 思路，另一个在前面的（32）。

丢失的数字：给定一个包含?[0, n]?中?n?个数的数组?nums?，找出?[0, n]?这个范围内没有出现在数组中的那个数。

异或特点：a ^ 0 = a;?

? ? ? ? ? ? ? ? ? a ^?a = 0;

? ? ? ? ? ? ? ? ? a ^ (b ^ c) = (a ^ b) ^ c;?

思路：用异或的几种规则可以想到，让一个数先异或数组中的数字一遍，再异或从0->n所有数字一遍，最后得到的数字就是丢失的数字。

下面的代码注释我也写的很详细了。

class Solution 
{
public:
    vector<int> missingTwo(vector<int>& nums) 
    {
        int ret=0;
        //异或数组内的
        for(auto e:nums)
        {
            ret ^= e;
        }
        //异或从1--N所有
        for(int i=1;i<=nums.size()+2;i++)
        {
            ret ^= i;
        }
        //走到这里ret已经是两个缺失的数字的异或了
        //接下来找最低位1
        int lowbit = ret&(-ret);
        int count = 0;
        while(lowbit!=1)
        {
            lowbit = lowbit>>1;
            count++;
        }
        //知道两个数在第count位就不一样了，以此分组
        int a = 0, b = 0;
        for(auto e:nums)
        {
            if(((e>>count)&1)==1)
            {
                a ^= e;
            }
            else
            {
                b ^= e;
            }
        }
        for(int i=1;i<=nums.size()+2;i++)
        {
            if(((i>>count)&1)==1)
            {
                a ^= i;
            }
            else
            {
                b ^= i;
            }
        }
        return {a,b};
    }
};