百度爱采购怎么优化排名_太原网页设计师招聘_网站推广的策略_数据查询网站

---

题目链接：

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

---

题目描述：

---

解法

a，b是缺失的两个数

1. 将所有的数异或在一起，得到tmp=nums^(1~N)。

   tmp=a^b

2. 找到tmp中，比特位上为1的那一位。（因为a和b是不一样的，所以异或后不为0，tmp上肯定有一位上比特位为1）

3. 根据x位的不同，把nums和1~N里面所有的数划分成两类异或

   一类是 第x 位为 1 的数，另一类是 第x 位为 0 的数。

   分别对这两类数进行异或操作，因为成对的数会抵消，所以最终分别得到两个缺失的数 a 和 b。

---

C++ 算法代码：

class Solution 
{public:vector<int> missingTwo(vector<int>& nums) {// 1. 将所有的数异或在一起int tmp = 0;for(auto x : nums) tmp ^= x;for(int i = 1; i <= nums.size() + 2; i++) tmp ^= i;// 2. 找出 a，b 中比特位不同的那一位int diff = 0;while(1){if(((tmp >> diff) & 1) == 1) break;else diff++;}// 3. 根据 diff 位的不同，将所有的数划分为两类来异或int a = 0, b = 0;for(int x : nums)if(((x >> diff) & 1) == 1) b ^= x;else a ^= x;for(int i = 1; i <= nums.size() + 2; i++)if(((i >> diff) & 1) == 1) b ^= i;else a ^= i;return {a, b};}
};

---

图解

例如：nums = [1, 2, 4, 5]，缺失的两个数是 3 和 6。

1. 异或所有数：1 ^ 2 ^ 4 ^ 5 = 2

2. 异或 1 到 6：2 ^ (1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6) = 3 ^ 6 = 5

3. 找到 x = 0

4. 分组：

   x 位为 1 的数：1, 3, 5 异或结果为 3

   x 位为 0 的数：2, 4, 6 异或结果为 6

5. 最终返回 {3, 6}