README.md

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

English Version

题目描述

给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？

以任意顺序返回这两个数字均可。

示例 1:

输入: [1]
输出: [2,3]

示例 2:

输入: [2,3]
输出: [1,4]

提示：

• nums.length <= 30000

解法

方法一：位运算

利用位运算的性质：

1. 对于任何数 $x$，都有 $x \oplus x = 0$
2. 异或运算满足结合律，即 $(a \oplus b) \oplus c = a \oplus (b \oplus c)$
3. lowbit 运算获取最低一位的 $1$ 及其后面的所有 $0$，公式为 lowbit(x) = x & (-x)

我们将 nums 中所有数进行异或到 $x$，再将 $[1,2..n]$ 的所有数也异或到 $x$。得到的 $x$ 是两个缺失的正整数的异或和。

然后我们运用 lowbit 获取最低一位的 $1$，那么这两个缺失的正整数在这一位上必然一个为 $1$，一个为 $0$。我们据此进行分组异或。最终得到两个缺失的正整数 $a$ 和 $b$。

时间复杂度 $O(n)$，空间复杂度 $O(1)$。其中 $n$ 为数组长度。

class Solution:
    def missingTwo(self, nums: List[int]) -> List[int]:
        n = len(nums) + 2
        xor = 0
        for v in nums:
            xor ^= v
        for i in range(1, n + 1):
            xor ^= i

        diff = xor & (-xor)
        a = 0
        for v in nums:
            if v & diff:
                a ^= v
        for i in range(1, n + 1):
            if i & diff:
                a ^= i
        b = xor ^ a
        return [a, b]

class Solution {
    public int[] missingTwo(int[] nums) {
        int n = nums.length + 2;
        int xor = 0;
        for (int v : nums) {
            xor ^= v;
        }
        for (int i = 1; i <= n; ++i) {
            xor ^= i;
        }
        int diff = xor & (-xor);
        int a = 0;
        for (int v : nums) {
            if ((v & diff) != 0) {
                a ^= v;
            }
        }
        for (int i = 1; i <= n; ++i) {
            if ((i & diff) != 0) {
                a ^= i;
            }
        }
        int b = xor ^ a;
        return new int[] {a, b};
    }
}

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int n = nums.size() + 2;
        int eor = 0;
        for (int v : nums) eor ^= v;
        for (int i = 1; i <= n; ++i) eor ^= i;

        int diff = eor & -eor;
        int a = 0;
        for (int v : nums)
            if (v & diff) a ^= v;
        for (int i = 1; i <= n; ++i)
            if (i & diff) a ^= i;
        int b = eor ^ a;
        return {a, b};
    }
};

func missingTwo(nums []int) []int {
	n := len(nums) + 2
	xor := 0
	for _, v := range nums {
		xor ^= v
	}
	for i := 1; i <= n; i++ {
		xor ^= i
	}
	diff := xor & -xor
	a := 0
	for _, v := range nums {
		if (v & diff) != 0 {
			a ^= v
		}
	}
	for i := 1; i <= n; i++ {
		if (i & diff) != 0 {
			a ^= i
		}
	}
	b := xor ^ a
	return []int{a, b}
}