题目解析

面试题 17.19. 消失的两个数字

算法讲解

我们将这两个数组异或在一起，最后的结果就是a ^ b(缺失的两个数字)的结果，这两个缺失的数字一定是不相同的，所以我们就寻找他们第一个比特位是1的那个位置，异或的原理是：相同为0， 不同为1，按照这个位置将数组划分成两部分，一部分是这一位上是1的，另一部分是这一位上是0的，然后将两个数组的两个部分异或在一起，就得到缺失的两个数字

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int n = nums.size() + 2;
        int sum = 0;
        for(auto e : nums)
            sum ^= e;
        for(int i = 1; i <= n; i++)
        {
            sum ^= i;
        } 
            //之后 sum 就是保存的缺失的两个数字的异或结果
        
        int ret1 = 0, ret2 = 0, index = 0;
        //寻找两个缺失数字的第一的不相同的比特位
        while((sum & (1 << index)) == 0)
        {
            index++;
        }
        index = (1 << index);

        //划分成两组
        for(auto e : nums)
        {
            if(e & index)
                ret1 ^= e;
            else
                ret2 ^= e;
        }
        for(int i = 1; i <= n; i++)
        {
            if(i & index)
                ret1 ^= i;
            else
                ret2 ^= i;
        }
        return {ret1, ret2};
    }
};