【LeetCode刷题】面试题 17.19. 消失的两个数字

1. 题目链接

2. 题目描述

3. 解题方法

例子假设：

数组A元素为 ：1 ，4，5

缺少的元素为：2， 3

那么所有整数就为1 ~ 5，我称这些整数为数组B

此时就有如下的图示：

第1步，此时将A、B两个数组的元素都异或起来，所得到的结果就是2 ^ 3，为了后面的讲解

我将2成为a，3称为b。

第2步，找到a和b（异或）比特位上为1的那一位

2 ： 0 1 0

3 ： 0 1 1

找到的这一位，我在这里叫做第x位

第3步，根据第x位的不同，划分两类进行异或求得结果

根据上面的例子

1 ： 0 0 1

5 ： 1 0 1

过程 ： 3 ^ 1 ^ 1 ^ 5 ^ 5 （相同的两个数字异或直接为0，0异或任何数字为数字本身）

这一类划分到 3 这里进行异或，就得到了唯一的3

4 ： 0 1 0

过程 ： 2 ^ 4 ^ 4 （相同的两个数字异或直接为0，0异或任何数字为数字本身）

这一类划分到 2 这里进行异或，就得到了唯一的2

4. 代码

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) 
    {
        // 1. 把所有相同的数都异或起来, 获得a ^ b
        int tmp = 0;
        for(auto e : nums) tmp ^= e;
        for(int i = 1; i <= nums.size() + 2; i++) tmp ^= i;

        // 2. 找到a ^ b 比特位为 1 的那一位
        int diff = 0;
        while(1)
        {
            if((tmp >> diff) & 1 == 1) break;
            else diff ++;
        }

        // 3. 划分两类数字
        int a = 0, b = 0;
        for(auto e : nums)
        {
            if((e >> diff) & 1 == 1) a ^= e;
            else b ^= e;
        }
        for(int i = 1; i <= nums.size() + 2; i++)
        {
            if((i >> diff) & 1 == 1) a ^= i;
            else b ^= i;
        }
        return {a, b};
    }
};

最后附上我的打卡记录，希望各位大佬可以监督我。