跳转至

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

题目描述

给定一个数组，包含从 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$ 为数组长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
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]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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};
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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};
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    func missingTwo(_ nums: [Int]) -> [Int] {
        let n = nums.count + 2
        var xor = 0

        for num in nums {
            xor ^= num
        }

        for i in 1...n {
            xor ^= i
        }

        let diff = xor & (-xor)

        var a = 0

        for num in nums {
            if (num & diff) != 0 {
                a ^= num
            }
        }

        for i in 1...n {
            if (i & diff) != 0 {
                a ^= i
            }
        }

        let b = xor ^ a
        return [a, b]
    }
}

评论