【位运算】消失的两个数字（hard）

题⽬链接：⾯试题 17.19. 消失的两个数字

题⽬描述：

给定⼀个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只⽤ O(1) 的
空间找到它们吗？
以任意顺序返回这两个数字均可。
⽰例 1:
输⼊: [1]
输出: [2,3]
⽰例 2:
输⼊: [2,3]
输出: [1,4]
提⽰：
nums.length <= 30000

解法（位运算）：

算法思路：
本题就是 268. 丢失的数字 + 260. 只出现⼀次的数字 III 组合起来的题。
先将数组中的数和 [1, n + 2] 区间内的所有数「异或」在⼀起，问题就变成了：有两个数出现了「⼀次」，其余所有的数出现了「两次」。进⽽变成了 260. 只出现⼀次的数字 III 这道题。

Java 算法代码：

class Solution{public int[] missingTwo(int[] nums) {// 1. 先把所有的数异或在⼀起int tmp = 0;for(int x : nums) tmp ^= x;for(int i = 1; i <= nums.length + 2; i++) tmp ^= i;// 2. 找出 a，b 两个数⽐特位不同的那⼀位int diff = 0;while(true){if(((tmp >> diff) & 1) == 1) break;else diff++;}// 3. 将所有的数按照 diff 位不同，分两类异或int[] ret = new int[2];for(int x : nums)if(((x >> diff) & 1) == 1) ret[1] ^= x;else ret[0] ^= x;for(int i = 1; i <= nums.length + 2; i++)if(((i >> diff) & 1) == 1) ret[1] ^= i;else ret[0] ^= i;return ret;}
}

求解方法是利用「异或」+「lowbit」。

由于我们明确了是在 [1,n+2] 中缺失了两个数，我们可以先通过异或 [1,n+2] 以及所有的 nums[i] 来得到缺失两个数值异或和 t。

我们知道异或结果二进制表示为 1 代表了两缺失值该位置数值不同（一个该位置 0，另一个该位置为 1），我们可以根据异或和 t 中任意一位为 1 的位置来将两个缺失值划分到两组中。

更加优雅的方式是使用 lowbit 操作：d = t & -t 可快速得到只保留 t 中最低位 1 的对应数值。

随后将 [1,n+2] 中满足 i & d != 0 的所有 i（含义为对应位置为 1 的数值）与 nums[i] 中满足 nums[i] & d != 0 的所有 nums[i]（含义为对应位置为 1 的数值） 进行异或，最终能够确定其中一个缺失值，再结合最开始的异或和 t 即可确定另外一个缺失值。

更简便代码

class Solution {public int[] missingTwo(int[] nums) {// 1. 先把所有的数异或在⼀起int n = nums.length + 2, cur = 0;for (int i = 1; i <= n; i++) cur ^= i;for (int x : nums) cur ^= x;// 2. 找出 a，b 两个数⽐特位不同的那⼀位int t = cur, d = cur & -cur;// 3. 将所有的数按照 diff 位不同，分两类异或cur = 0;for (int i = 1; i <= n; i++) {if ((d & i) != 0) cur ^= i;}for (int x : nums) {if ((d & x) != 0) cur ^= x;}return new int[]{cur, t ^ cur};}
}

时间复杂度：O(n)
空间复杂度：O(1)
注意：
是if ((d & i) != 0) cur ^= i;不是if (d & i != 0) cur ^= i;（必须加括号）