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

约 4 分钟
文章信息 8 个分类 2 个标签
分类
LeetCode CodeTop 简单 未解决 2-5 字节 阿里 小红书
标签
数组 二分查找

题目描述

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

image-20260928230453566

image-20260928230453567

题意分析

给定严格递增的正整数数组，从所有正整数 1, 2, 3, ... 中去掉数组里已经出现的数，找剩下序列中的第 k 个，排名从 1 开始。

缺失统计从正整数 1 开始，不是从数组首项开始。答案可能小于首项、位于相邻元素之间，也可能大于末项，不需要限制在数组原有数值范围内。

解法：二分缺失数量边界

核心思路

[!blue]

到数组下标 i 为止，区间 [1, arr[i]] 一共有 arr[i] 个正整数，其中数组已出现 i + 1 个，所以缺失数量是 missing(i) = arr[i] - i - 1。因为 arr[i] 本身存在，这也就是它之前的缺失数量。

数组严格递增，相邻值至少增加一，而下标也只增加一，因此这个缺失数量不会下降。可以二分查找第一个满足 missing(i) >= k 的位置，记为 left，而不用逐个枚举缺失的正整数。

这个边界的含义是：它前面的数组元素之前还没有缺够 k 个数，因此这些元素都小于答案；从这个位置开始，已经有至少 k 个数缺失，所以这些元素都大于答案。若没有满足条件的位置，就让 left = n，表示答案大于全部数组元素。

因而答案之前恰好有 left 个已经出现的正整数。设答案为 x，从 1 到 x 中包含 k 个缺失数和 left 个存在数，两类刚好构成全部 x 个正整数，所以 x = k + left。这个公式同时覆盖答案在首项之前或末项之后的情况。

解题步骤

  1. 使用左闭右开的二分区间，令 left = 0、right = arr.length。
  2. 取中点 mid，计算它之前的缺失数量 arr[mid] - mid - 1。
  3. 若不足 k，中点及其左侧都不是目标边界，令 left = mid + 1。
  4. 否则中点已经满足条件，保留它并继续向左查找，令 right = mid。
  5. 两边相遇后，返回 left + k，不需要读取可能等于数组长度的 arr[left]。

代码实现

class Solution {
    public int findKthPositive(int[] arr, int k) {
        int left = 0;
        // 右开边界允许最终位置等于数组长度，循环不会读取这个边界下标。
        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
    // 右开边界允许最终位置等于数组长度，循环不会读取这个边界下标。
    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+1))$。
  • 空间复杂度：$O(1)$。

关键点总结

[!green]

  • 数值减去已出现数量，得到的是累计缺失数量，它具有二分需要的单调性。
  • 寻找第一个达到 k 的边界，才能知道答案之前有多少个已存在元素。
  • k + left 来自存在与缺失两类正整数的计数，不依赖答案位于某个数组元素附近。

易错点总结

[!yellow]

  • 缺失数量写成 arr[i] - i，忘了下标 i 对应已经出现 i + 1 个数，会多算一个。
  • 缺失数量等于 k 时立即返回中点，可能落在一段相同计数的后部，应继续找第一个满足位置。
  • 将右边界限制为最后一个真实下标后又强行读取结果，会漏掉答案超过末项的情况。
  • 返回 arr[left]，得到的是一个已经存在的数，而且 left = n 时还会越界。
  • 在允许重复的数组上照搬计数式，会把重复项当成不同的已出现正整数，前提不再成立。

相似题目

题目 难度 关联与区别
1060. 有序数组中的缺失元素 中等 本题从正整数1开始计缺失值，原题以数组首项为起点，前缀缺失计数基准不同。
163. 缺失的区间 简单 缺失值组成有序间隙，本题按每个间隙的大小跳过，定位第k项而非输出全部区间。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/61279291
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！