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

题目描述

这是 LeetCode 上的 面试题 17.19. 消失的两个数字 ，难度为 困难。

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

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

示例 1:

1
2
3
输入: [1]

输出: [2,3]

示例 2:
1
2
3
输入: [2,3]

输出: [1,4]

提示：

  • $nums.length <= 30000$

数学

根据题意，给定 nums 的长度为 $m$ 且缺失了两个数，所有的 $nums[i]$ 加上缺失数字组成连续排列长度为 $n = m + 2$。

根据等差数量求和公式可知，补齐后的排列总和为 $\frac{n \times (1 + n)}{2}$，补全后的理论总和与实际总和之间的差值 $cur = \frac{n \times (1 + n)}{2} - \sum_{i = 0}^{m - 1}nums[i]$ 为缺失数值之和。

根据补全后数值各不相同可知，两者必不可能同时位于 $t = \left \lfloor \frac{cur}{2} \right \rfloor$ 的同一侧（偏大、偏小或数值重复），因此我们可以计算 $[1, t]$ 范围内的理论总和与实际总和之间的差值来确定其一（将问题转换为求解缺失一值），再结合缺失两值之和 $sum$ 算得答案。

Java 代码：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int[] missingTwo(int[] nums) {
        int n = nums.length + 2, cur = n * (1 + n) / 2;
        for (int x : nums) cur -= x;
        int sum = cur, t = cur / 2;
        cur = t * (1 + t) / 2;
        for (int x : nums) {
            if (x <= t) cur -= x;
        }
        return new int[]{cur, sum - cur};
    }
}

TypeScript 代码：
1
2
3
4
5
6
7
8
9
10
function missingTwo(nums: number[]): number[] {
    let n = nums.length + 2, cur = Math.floor(n * (1 + n) / 2)
    for (let x of nums) cur -= x
    let sum = cur, t = Math.floor(cur / 2)
    cur = Math.floor(t * (1 + t) / 2)
    for (let x of nums) {
        if (x <= t) cur -= x
    }
    return [cur, sum - cur]
};

Python 代码：
1
2
3
4
5
6
7
class Solution:
    def missingTwo(self, nums: List[int]) -> List[int]:
        n = len(nums) + 2
        cur = n * (1 + n) // 2 - sum(nums)
        tot, t = cur, cur // 2
        cur = t * (1 + t) // 2 - sum([x for x in nums if x <= t])
        return [cur, tot - cur]

  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(1)$

异或

另外一类求解方法是利用「异或」+「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 即可确定另外一个缺失值。

Java 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int[] missingTwo(int[] nums) {
        int n = nums.length + 2, cur = 0;
        for (int i = 1; i <= n; i++) cur ^= i;
        for (int x : nums) cur ^= x;
        int t = cur, d = cur & -cur;
        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};
    }
}

TypeScript 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
function missingTwo(nums: number[]): number[] {
    let n = nums.length + 2, cur = 0
    for (let i = 1; i <= n; i++) cur ^= i
    for (let x of nums) cur ^= x
    const t = cur, d = cur & -cur
    cur = 0
    for (let i = 1; i <= n; i++) {
        if ((d & i) != 0) cur ^= i
    }
    for (let x of nums) {
        if ((d & x) != 0) cur ^= x
    }
    return [cur, t ^ cur]
};

Python 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def missingTwo(self, nums: List[int]) -> List[int]:
        n, cur = len(nums) + 2, 0
        for i in range(1, n + 1):
            cur ^= i
        for x in nums:
            cur ^= x
        t, d = cur, cur & -cur
        cur = 0
        for i in range(1, n + 1):
            if d & i:
                cur ^= i
        for x in nums:
            if d & x:
                cur ^= x
        return [cur, t ^ cur]

  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(1)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.面试题 17.19 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。