LeetCode 1539. 第 k 个缺失的正整数

2025-10-29 HGNULB 约 11 分钟

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

分类

题目描述

✅ 1539. 第 k 个缺失的正整数

题意分析

给一个严格递增的正整数数组 arr，把它看成从完整正整数序列 1, 2, 3, … 里挖掉了若干个数之后剩下的部分，要求返回被挖掉的那些数中的第 k 个（按从小到大排）。

"严格递增"这四个字给了两个信息：一是数组里没有重复元素，每个下标对应一个确定的值；二是数组本身有序，这是任何二分的前提。题目专门强调它，就是在暗示不要停留在线性扫描。

关键的量化关系是：如果一个数都没缺，arr[i] 应该恰好等于 i + 1（下标从 0 开始）。所以 arr[i] - (i + 1) 就是"在 arr[i] 之前一共缺了多少个正整数"。因为数组严格递增，相邻元素至少差 1，这个缺失量随下标单调不减——它要么保持不变（相邻两数连续），要么增加（中间有空档）。单调性一出现，二分就有了着力点。

约束是 1 ≤ arr.length ≤ 1000、1 ≤ k ≤ 1000，规模小到线性扫描完全够用。但这恰恰是这题的陷阱：能过不等于答对。面试里给出 $O(n)$ 之后，下一句一定是"数组是有序的，能不能做到 $O(\log n)$"，所以本文直接按二分来写。

边界有三档必须想清楚。第一档，答案落在 arr[0] 之前：arr = [2, 3, 4]、k = 1 时答案是 1，此时数组里没有任何元素排在答案前面。第二档，答案夹在数组中间：arr = [2, 3, 4, 7, 11]、k = 5 时答案是 9。第三档，答案超出 arr 的最后一个元素：arr = [1, 2, 3, 4]、k = 2 时答案是 6，二分区间必须容得下这种"跑出数组右端"的情况。

解法：二分缺失数量边界

核心思路

暴力做法有两种。一是从 1 开始逐个数往上试，用哈希集合判断在不在 arr 里，数到第 k 个不在的就返回；这需要额外的 $O(n)$ 空间，而且要走到的位置可能是 n + k。二是双指针扫一遍数组，用一个计数器累计已经跳过了多少个数，一旦累计到 k 就停；这是 $O(n)$ 时间 $O(1)$ 空间，已经很干净了。瓶颈在于：数组是有序的，而我们却在线性地走它——有序结构的信息完全没有被利用。

定义 missing(i) = arr[i] - i - 1，表示"数组前 i + 1 个元素覆盖的范围内，一共缺失了几个正整数"。这个函数的单调不减性质前面已经论证过。既然它单调，那么"缺失量是否已经达到 k"就是一个从假到真、只翻转一次的谓词，标准的二分找左边界场景。

于是目标明确为：找到最小的下标 left，使得 missing(left) ≥ k；如果所有下标都不满足，left 落在 n。

二分维护的循环不变量是：区间 [0, left) 内的元素缺失量全部严格小于 k，区间 [right, n) 内的元素缺失量全部大于等于 k，答案下标就夹在 [left, right) 里。初始时 left = 0、right = n，两个已知区间都为空，不变量平凡成立。每轮取中点 mid：若 missing(mid) < k，说明 mid 及其左侧都属于"不足 k"的一段，把 left 推到 mid + 1；否则 mid 本身就是一个候选，把 right 收到 mid（保留 mid，不能写成 mid - 1）。区间每轮至少缩短一半，left == right 时循环结束。

最后一步是把下标翻译成答案，这是本题真正的巧妙之处：循环结束时 left 的含义是"缺失量小于 k 的数组元素个数"，也就是在最终答案之前，还夹着 left 个确实存在于 arr 中的数。从 1 数到答案，一共要经过 left 个存在的数和 k 个缺失的数，所以答案就是第 left + k 个正整数，即 left + k。

这个公式的好处是它自动统一了前面说的三档边界，不需要任何分支：答案在数组前面时 left = 0，答案就是 k；答案超出数组末尾时 left = n，答案是 n + k。

解题步骤

把二分区间初始化为 left = 0、right = arr.length。为什么右边界取 n 而不是 n - 1：n 是一个合法的"答案下标"取值，它表示"数组里所有元素的缺失量都不够 k，答案落在数组末尾之后"。若右边界写成 n - 1，arr = [1,2,3,4]、k = 2 这种情况就永远收敛不到 left = 4，返回值会小 1。

循环条件用 left < right，中点用 left + (right - left) / 2。为什么不用 left <= right：这是左闭右开区间的二分模板，left == right 时区间为空、答案已经确定，继续循环会越界。中点这样写而不是 (left + right) / 2，是为了避免两个大下标相加时的整型溢出——本题 n ≤ 1000 溢不了，但这是该固化的肌肉记忆。

计算 missing = arr[mid] - mid - 1。为什么是减 mid 再减 1：无缺失时下标 mid 上应该是 mid + 1，实际值 arr[mid] 比它大多少，就说明前面被挖走了多少个。少减那个 1 会让整条判定线整体偏移一格。

missing < k 时执行 left = mid + 1。为什么可以放心跳过 mid：mid 处缺失量还不够 k，说明第 k 个缺失数一定排在 arr[mid] 之后，mid 不可能是我们要找的左边界，排除掉它是安全的。

否则执行 right = mid。为什么保留 mid 而不是 mid - 1：mid 处缺失量已经达到 k，它本身就是一个满足条件的候选，可能正是最小的那个。写成 mid - 1 会把唯一的答案丢掉，二分退化成漏解。

返回 left + k，而不是 arr[left] 或 arr[left] - 1。为什么：left 是下标不是数值，题目要的是缺失的那个正整数。left 个存在的数加上 k 个缺失的数，答案就排在第 left + k 位。而且 left 可能等于 n，此时 arr[left] 直接越界。

以 arr = [2, 3, 4, 7, 11]、k = 5 走一遍（n = 5，先列出各下标的缺失量：missing(0) = 2-0-1 = 1，missing(1) = 3-1-1 = 1，missing(2) = 4-2-1 = 1，missing(3) = 7-3-1 = 3，missing(4) = 11-4-1 = 5）：

初始 left = 0、right = 5。

第一轮：mid = 0 + (5-0)/2 = 2，missing(2) = 1 < 5，答案在右侧，left = 3。区间收为 [3, 5)。

第二轮：mid = 3 + (5-3)/2 = 4，missing(4) = 5 ≥ 5，mid = 4 是候选，right = 4。区间收为 [3, 4)。

第三轮：mid = 3 + (4-3)/2 = 3，missing(3) = 3 < 5，left = 4。区间收为 [4, 4)，为空。

循环退出，left = 4，返回 4 + 5 = 9。

核对一下：arr 覆盖到 11，缺失的正整数依次是 1, 5, 6, 8, 9, 10，第 5 个正是 9。再从公式的含义验证：答案 9 之前存在于数组里的数是 2, 3, 4, 7 共 4 个，正好等于 left = 4；9 是第 4 + 5 = 9 个正整数，吻合。

再补两个极端用例。arr = [2, 3, 4]、k = 1：missing 全为 1 ≥ 1，二分会一路把 right 压到 0，left = 0，返回 0 + 1 = 1，正确。arr = [1, 2, 3, 4]、k = 2：missing 全为 0 < 2，left 一路推到 4，返回 4 + 2 = 6，正确——这正是右边界必须取 n 才能到达的位置。

代码实现

class Solution {
    public int findKthPositive(int[] arr, int k) {
        int left = 0;
        // 右边界取 n 而非 n - 1，才容得下"答案落在数组末尾之后"的情况。
        int right = arr.length;

        while (left < right) {
            int mid = left + (right - left) / 2;
            // 无缺失时 arr[mid] 应为 mid + 1，差值就是前面缺了几个正整数。
            int missing = arr[mid] - mid - 1;

            if (missing < k) {
                left = mid + 1;
            } else {
                // mid 本身就是候选，收缩时必须保留它。
                right = mid;
            }
        }

        // left 是答案之前仍然存在的数的个数，答案即第 left + k 个正整数。
        return left + k;
    }
}

func findKthPositive(arr []int, k int) int {
    left := 0
    // 右边界取 n 而非 n - 1，才容得下"答案落在数组末尾之后"的情况。
    right := len(arr)

    for left < right {
        mid := left + (right-left)/2
        // 无缺失时 arr[mid] 应为 mid + 1，差值就是前面缺了几个正整数。
        missing := arr[mid] - mid - 1

        if missing < k {
            left = mid + 1
        } else {
            // mid 本身就是候选，收缩时必须保留它。
            right = mid
        }
    }

    // left 是答案之前仍然存在的数的个数，答案即第 left + k 个正整数。
    return left + k
}

复杂度分析

时间复杂度：$O(\log n)$。凭什么：每轮循环把区间 [left, right) 的长度至少砍掉一半，从 n 缩到 0 需要 $O(\log n)$ 轮；循环体内只有一次取中点、一次减法和一次比较，全是常数操作。相比双指针扫描的 $O(n)$，这才是"严格递增"这个条件该换来的收益。

空间复杂度：$O(1)$。凭什么：只用了 left、right、mid、missing 四个整型变量，既没有建哈希集合，也没有递归调用栈（写成迭代二分而非递归二分）。

关键点总结

把"找第 k 个缺失元素"改写成"找第一个缺失量达到 k 的下标"，是本题的核心动作。原问题的对象是数值、无序可循；改写后的对象是下标、且判定函数单调，二分才有立足点。遇到"第 k 个满足某性质的数"，都可以试着构造一个关于下标的单调计数函数。

arr[i] - i - 1 这个式子要能当场推出来而不是背下来。推法是固定的：先写出"理想情况下这个位置该是什么值"（i + 1），再用实际值减去理想值，差额就是被挖走的数量。这套"实际减理想"的思路在很多"缺失/重复元素"题里通用。

二分找左边界的模板要固定成左闭右开：right 初值取 n、循环条件 left < right、命中时 right = mid 而不是 mid - 1、退出后直接用 left。四条配套使用才自洽，混搭闭区间模板必错。

右边界能否取到 n，取决于"答案不在数组内"是否是合法结果。本题答案本来就是一个不在数组里的数，所以 left = n 是完全正常的收敛结果，右边界必须留出这一格。写二分前先问一句"下标的合法取值范围到底是哪些"，能省掉大量差一调试。

把下标翻译回答案的那一步往往比二分本身更容易错。left + k 这个公式之所以成立，是因为 left 恰好是"排在答案前面的存在数的个数"；能用这句话解释清楚，就说明真的理解了，而不是凑出来的。

面试视角：先给出 $O(n)$ 的双指针解并说明它已经能过本题数据，再主动指出"数组严格递增"意味着可以二分到 $O(\log n)$，然后给出上面的写法。被追问时重点讲三件事——单调性从哪来、右边界为什么是 n、left + k 的组合意义。这题考的就是能不能把一个非典型问题掰成标准二分。

易错点总结

缺失量写成 arr[mid] - mid：arr = [1,2,3,4]、k = 2 时每个位置算出的缺失量都是 1 而不是 0，判定整体偏移，left 停在错误位置，返回 5 而正确答案是 6。

右边界初始化成 arr.length - 1：arr = [1,2,3,4]、k = 2 时 left 最多推到 3，返回 3 + 2 = 5，比正确答案 6 小 1——所有"答案在数组之后"的用例统一错一位。

命中分支写成 right = mid - 1：arr = [2,3,4]、k = 1 时唯一的候选下标 0 会被跳过，right 变成 -1，循环条件 left < right 立刻不成立，left 停在 0 看似侥幸正确，但换成 arr = [2,3,4,7,11]、k = 3 就会漏掉真正的左边界而返回错值。

返回 arr[left] 或 arr[left] - 1：题目要的是缺失的数，而 arr[left] 是存在的数；更致命的是 left 可以等于 arr.length，arr = [1,2,3,4]、k = 2 时直接数组越界抛异常。

循环条件写成 left <= right 却保持 right = mid：missing(mid) ≥ k 时 right 不再减小，left == right == mid 这一轮会无限重复，程序死循环超时。

不足 k 的分支写成 left = mid：同样构成死循环，arr = [2,3,4,7,11]、k = 5 在 left = 3、right = 4 时 mid 恒为 3，left 永远推不动。

判定条件写成 missing <= k 走左移分支：arr = [2,3,4,7,11]、k = 5 时 missing(4) = 5 会被误判为"还不够"，left 被推到 5，返回 10 而不是 9。左边界二分的判定必须是严格小于。

把 k 理解成"数组中第 k 个位置对应的缺失数"：arr = [2,3,4]、k = 1 会去看 arr[1] 相关的量，返回 2 或 3；正确答案是 1，也就是排在整个数组之前的那个缺失数。

改用哈希集合从 1 开始逐个试：虽然本题数据小能过，但空间从 $O(1)$ 涨到 $O(n)$，而且完全没利用有序性，面试里说出这个方案后基本会被要求重做。

中点写成 (left + right) / 2：本题 n ≤ 1000 不会溢出，但换成 10^9 级下标的题目就会因为相加越界得到负数中点，进而数组越界。这是应该无条件写成 left + (right - left) / 2 的原因。

相似题目

题目	难度	考察点
704. 二分查找	简单	最基础的等值二分，先在这里把左闭右开模板的四个配套细节固定下来
35. 搜索插入位置	简单	同样是找左边界且答案可以等于 `n`，与本题右边界取 `n` 的理由完全一致
34. 在排序数组中查找元素的第一个和最后一个位置	中等	左右边界各二分一次，是对同一模板正反两个方向的完整训练
268. 丢失的数字	简单	只缺一个数且范围固定，可用求和作差或异或直接 $O(n)$ 得到，无需二分
41. 缺失的第一个正数	困难	数组无序且要求 $O(n)$ 时间 $O(1)$ 空间，靠原地置换把值放回下标位而不是二分
540. 有序数组中的单一元素	中等	判定谓词建立在下标奇偶配对是否被破坏上，同样是"构造单调性再二分"
162. 寻找峰值	中等	数组整体无序，靠局部相邻大小关系保证二分方向正确，展示单调性的另一种来源
875. 爱吃香蕉的珂珂	中等	二分的对象是答案值域而非数组下标，判定函数需要 $O(n)$ 现算