LeetCode 1060. 有序数组中的缺失元素

2022-01-18 HGNULB 约 10 分钟

文章信息 7 个分类 2 个标签

分类

题目描述

✅ 1060. 有序数组中的缺失元素

题意分析

给定一个严格递增、元素互不相同的整数数组 nums，把它看成从 nums[0] 开始的一段连续整数被挖掉了若干个数之后的残留，要求返回被挖掉的第 k 个数。

关键在于「从哪里开始数」。计数的起点是 nums[0] 而不是 $1$，也不是 $0$。以 [4, 7, 9, 10] 为例，缺失的数依次是 $5, 6, 8$，而不是 $1, 2, 3$。这个约定读错就整题皆错。

约束里数组长度可以到 $5 \times 10^4$，而 k 可以大到 $10^8$。k 的量级远超数组长度，这是一个强烈的信号：任何按 k 逐个往上数的做法都不可行，必须用与 k 无关的方式定位。

边界要提前分清两类：一类是答案夹在数组的某两个相邻元素之间，另一类是数组内部的空缺加起来都不够 k 个、答案落在最后一个元素之后。后者的典型例子是 [1, 2, 4] 配 k = 3，数组里只缺了一个 $3$，剩下两个要从 $4$ 往后接着数，答案是 $6$。此外数组完全连续、没有任何空缺时，答案必然全部落在末尾之后。

解法：缺失数量上的二分查找

核心思路

暴力做法是从 nums[0] 开始逐个整数往上试，遇到不在数组里的就把计数加一，数到第 k 个为止。它的代价与答案的大小成正比，k 到 $10^8$ 时必然超时。瓶颈很明确：把「第 k 个」这件事当成了必须一步步累加出来的量。

换一个角度。对下标 i，考察从 nums[0] 到 nums[i] 这段闭区间里已经缺了多少个数。如果一个数都不缺，这段应当恰好有 $i + 1$ 个连续整数，即 nums[i] 应等于 nums[0] + i。实际的 nums[i] 比它大出多少，就说明中间被挖走了多少个。于是定义 $\text{missing}(i) = nums[i] - nums[0] - i$，它就是「到下标 i 为止累计缺失的数量」。

这个函数有一条决定性的性质：因为数组严格递增，相邻两项至少差 $1$，所以 $\text{missing}(i + 1) - \text{missing}(i) = nums[i + 1] - nums[i] - 1 \ge 0$，即 $\text{missing}$ 单调不减。一个单调不减的数组上找「第一个不小于 k 的位置」，正是二分的标准形态，代价与 k 的大小无关。

维持的不变量是：二分区间 [left, right] 始终包含第一个满足 $\text{missing}(i) \ge k$ 的下标。每轮用 mid 处的缺失量与 k 比较，若已达标则该下标本身仍是候选，把 right 收到 mid；否则 mid 及其左侧全部不达标，把 left 推到 mid + 1。区间每轮至少缩小一半，退出时 left 与 right 重合于目标下标。

找到这个下标 left 之后还要还原出具体的数值。由定义可知，left - 1 处累计缺失 $\text{missing}(left - 1)$ 个，且这些缺失都在 nums[left - 1] 之前或恰好因它而止；而第 k 个缺失数在 left 处才被数到，所以它一定落在 nums[left - 1] 与 nums[left] 这段空隙里。空隙内的数是连续的，从 nums[left - 1] 往上第 $k - \text{missing}(left - 1)$ 个就是答案。

前提是这个下标真的存在。若 $\text{missing}(n - 1) < k$，说明整个数组的空缺加起来都不够 k 个，二分找不到目标，必须先单独处理：从 nums[n - 1] 往后每个数都缺，再往上数 $k - \text{missing}(n - 1)$ 个即可。

解题步骤

先定义辅助函数 $\text{missing}(i) = nums[i] - nums[0] - i$。把它抽成函数而不是散落在各处手写表达式，是为了保证二分判定和最后回推数值时用的是同一个定义，减少符号写错的机会。

先算 $\text{missing}(n - 1)$ 并与 k 比较。若小于 k，直接返回 nums[n - 1] + k - missing(n - 1)。这一步必须放在二分之前，因为它是二分的前置条件：目标下标不存在时二分不会报错，只会静静地收敛到一个错误的位置。

在 [0, n - 1] 上二分。左界取 $0$ 是因为 $\text{missing}(0) = 0$，当 k 至少为 $1$ 时它一定不达标，不会污染结果；右界取 $n - 1$ 是因为上一步已经保证了 $\text{missing}(n - 1) \ge k$，答案下标一定在区间内。

循环条件用 left < right，只在两者分离时继续。mid 取 left + (right - left) / 2 会向下取整，配合「达标时 right = mid、不达标时 left = mid + 1」，区间每轮真正收缩，不会在 left 与 mid 相等时原地打转。

退出后 left 就是第一个缺失量不小于 k 的下标，且由于 $\text{missing}(0) = 0 < k$，left 至少为 $1$，left - 1 不会越界。

返回 nums[left - 1] + k - missing(left - 1)。用 left - 1 而不是 left 作为基准，是因为第 k 个缺失数还没被 nums[left - 1] 数到，它躺在这个元素之后的空隙里。

以 nums = [4, 7, 9, 10]、k = 3 走一遍：先算各下标的缺失量，$\text{missing}(0) = 4 - 4 - 0 = 0$，$\text{missing}(1) = 7 - 4 - 1 = 2$，$\text{missing}(2) = 9 - 4 - 2 = 3$，$\text{missing}(3) = 10 - 4 - 3 = 3$，确实单调不减。

由于 $\text{missing}(3) = 3$ 不小于 k = 3，不走末尾分支，进入二分。初始 left = 0、right = 3。第一轮 mid = 0 + (3 - 0) / 2 = 1，$\text{missing}(1) = 2 < 3$ 不达标，left 变为 $2$。第二轮 left = 2、right = 3，mid = 2 + (3 - 2) / 2 = 2，$\text{missing}(2) = 3 \ge 3$ 达标，right 变为 $2$。此时 left 与 right 都等于 $2$，循环结束。

于是目标下标为 $2$，before 取 $\text{missing}(1) = 2$，返回 $nums[1] + k - before = 7 + 3 - 2 = 8$。核对一下：[4, 7, 9, 10] 缺的数依次是 $5, 6, 8$，第 $3$ 个正是 $8$，与推演一致。

再看落在末尾之后的情形，nums = [1, 2, 4]、k = 3。$\text{missing}(2) = 4 - 1 - 2 = 1$ 小于 $3$，走前置分支，返回 $nums[2] + k - 1 = 4 + 3 - 1 = 6$。核对：数组只缺了 $3$，继续往后缺 $5$、$6$，第 $3$ 个正是 $6$。

代码实现

class Solution {
    // 如果最后一个元素之前缺失数量仍小于 k，答案在数组右侧，可以直接向后补差值。
    public int missingElement(int[] nums, int k) {
        int n = nums.length;
        int missingLast = missing(nums, n - 1);
        if (missingLast < k) {
            return nums[n - 1] + k - missingLast;
        }

        int left = 0;
        int right = n - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (missing(nums, mid) >= k) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        int before = missing(nums, left - 1);
        return nums[left - 1] + k - before;
    }

    private int missing(int[] nums, int index) {
        return nums[index] - nums[0] - index;
    }
}

func missingElement(nums []int, k int) int {
    // 如果最后一个元素之前缺失数量仍小于 k，答案在数组右侧，可以直接向后补差值。
    n := len(nums)
    missing := func(index int) int {
        return nums[index] - nums[0] - index
    }

    missingLast := missing(n - 1)
    if missingLast < k {
        return nums[n-1] + k - missingLast
    }

    left, right := 0, n-1
    for left < right {
        mid := left + (right-left)/2
        if missing(mid) >= k {
            right = mid
        } else {
            left = mid + 1
        }
    }

    before := missing(left - 1)
    return nums[left-1] + k - before
}

复杂度分析

时间复杂度：$O(\log n)$，其中 n 是数组长度。前置判断只做一次常数运算；二分每轮把候选区间对半砍，最多 $\lceil \log_2 n \rceil$ 轮，每轮内部只是一次减法和一次比较。整个过程与 k 的大小无关，这正是它能扛住 $k \le 10^8$ 的原因。

空间复杂度：$O(1)$，只用了 left、right、mid、before 等常数个整型变量，缺失量是按下标即时算出的，没有额外开数组来预存前缀信息。

关键点总结

遇到「第 k 个满足某性质的数」而 k 的量级远大于数据规模时，第一反应应当是找一个关于下标单调的计数函数，把「逐个数」换成「在计数上二分」。本题的 $nums[i] - nums[0] - i$ 就是这样一把钥匙。

单调性要能证明而不是靠感觉。这里依据的是「严格递增数组相邻差至少为 $1$」，从而缺失量的一阶差分非负。面试时把这句话说出来，比直接写二分更能体现思路是推出来的。

二分只负责定位「第一个达标的下标」，最终数值还要靠区间内的连续性线性回推。定位与还原是两个独立的步骤，混在一起写最容易把基准取错一位。

二分之前必须确认目标存在。当整个数组都不达标时，二分不会抛异常，只会收敛到一个看起来正常但语义错误的位置，这类静默错误比崩溃更难查，所以要用前置判断挡在外面。

面试视角：这题的高频追问是「如果数组允许有重复元素怎么办」。答案是缺失量的差分变成 $nums[i + 1] - nums[i] - 1$，可能取到 $-1$，单调性被破坏，二分不再成立，需要先去重。能主动提出这个前提依赖，说明你理解的是原理而不是模板。

面试视角：另一个常见追问是「为什么不预处理前缀缺失数组再二分」。要能指出缺失量有闭式表达式，$O(1)$ 就能算出任意下标的值，额外开 $O(n)$ 数组是纯粹的浪费，这体现了对空间开销的敏感度。

易错点总结

错误写法：省掉 $\text{missing}(n - 1) < k$ 的前置判断，直接进入二分 → 以 nums = [1, 2, 4]、k = 3 为例，所有下标的缺失量都小于 $3$，二分把 left 一路推到 $2$，before 取到 $\text{missing}(1) = 0$，返回 $2 + 3 - 0 = 5$，而正确答案是 $6$。

错误写法：把二分判定写成 $\text{missing}(mid) > k$ → 找到的是第一个严格大于 k 的下标。以 [4, 7, 9, 10]、k = 3 为例，没有任何下标的缺失量大于 $3$，left 收敛到 $3$，返回 $nums[2] + 3 - 3 = 9$，而 $9$ 本身就在数组里，正确答案是 $8$。

错误写法：最后返回 nums[left] + k - missing(left) → 基准取成了达标位置本身。以 [4, 7, 9, 10]、k = 3 为例，得到 $9 + 3 - 3 = 9$，把答案推到了空隙的右端点上，正确答案是 $8$。

错误写法：以为缺失是从 $1$ 开始数的 → 以 [4, 7, 9, 10]、k = 1 为例会答出 $1$，但题目定义的第一个缺失数是 $5$。这个误读会让所有样例同时错，却常常被归咎于二分写错。

错误写法：直接返回 nums[0] + k → 以 [4, 7, 9, 10]、k = 1 恰好得到 $5$ 而蒙混过关，但 k = 3 时得到 $7$，$7$ 本身就在数组里，说明这个式子完全忽略了中间存在的元素。

错误写法：把 $\text{missing}(i)$ 写成 nums[i] - i 而漏掉减 nums[0] → 以 [4, 7, 9, 10] 为例 $\text{missing}(0)$ 变成 $4$，只要 $k \le 4$ 二分就在下标 $0$ 停下，随后访问 nums[-1] 直接越界。

错误写法：二分右界初始化为 n → mid 有机会取到 $n - 1$ 之上的位置，missing 里读 nums[n] 立刻越界；即便侥幸没越界，区间也包含了不存在的下标，语义已经失真。

错误写法：循环条件写成 left <= right 却仍用 right = mid 更新 → 当三者重合且判定达标时 right 不再变化，区间不收缩，程序陷入死循环直至超时。

错误写法：mid 写成 (left + right) / 2 → 本题下标不超过 $5 \times 10^4$ 不会溢出，但同样的模板一旦用到对数值域二分的题目上，两个大整数相加就会越过 int 上界变成负数，mid 落到区间之外。

错误写法：认为数组可能含重复元素而加上跳过相等项的逻辑 → 题目保证严格递增，多写的分支不仅无用，还可能在某些实现里让 left 跳过真正的目标下标，把正确的定位破坏掉。

相似题目

题目	难度	考察点
1539. 第 k 个缺失的正整数	简单	计数起点固定为 $1$，缺失量简化为 $arr[i] - i - 1$，无需处理起点偏移
540. 有序数组中的单一元素	中等	单调判定来自配对的奇偶性而非计数，考察如何自造二分谓词
34. 在排序数组中查找元素的第一个和最后一个位置	中等	同一份数据上分别求左边界与右边界，训练两种收缩写法的对称性
278. 第一个错误的版本	简单	判定函数由外部接口给出，是「找第一个达标位置」这一模板的最简形态
162. 寻找峰值	中等	数组整体无序，靠局部斜率决定收缩方向，说明二分不必依赖全局有序