文章目录
- 题目链接:
- 题目描述:
- 解法
- 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
异或结果为3
x
位为 0 的数:2, 4, 6
异或结果为6
-
最终返回
{3, 6}