文章目录
- 题目链接：
- 题目描述：
- 解法
- C++ 算法代码：
- 图解
题目链接：
面试题 17.19. 消失的两个数字
题目描述：
解法
a，b是缺失的两个数
将所有的数异或在一起，得到
tmp=nums^(1~N)。
tmp=a^b找到
tmp中，比特位上为1的那一位。（因为a和b是不一样的，所以异或后不为0，tmp上肯定有一位上比特位为1）根据
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 ^ 2 ^ 4 ^ 5 = 2 -
异或
1到6：2 ^ (1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6) = 3 ^ 6 = 5 -
找到
x = 0 -
分组：
x位为 1 的数：1, 3, 5异或结果为3x位为 0 的数：2, 4, 6异或结果为6 -
最终返回
{3, 6}
