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

1. 题目链接

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

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 ^ bint 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};}
};

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