---

1539. 第 k 个缺失的正整数

• 标签：数组、二分查找
• 难度：简单

题目链接

• 1539. 第 k 个缺失的正整数 - 力扣

题目大意

描述：给定一个严格递增的正整数数组 $arr$ 和一个整数 $k$。

要求：返回数组中第 $k$ 个缺失的正整数。

说明：

• $1 \le arr.length \le 1000$。
• $1 \le arr[i] \le 1000$。
• $1 \le k \le 1000$。

示例：

• 示例 1：

输入：arr = [2,3,4,7,11], k = 5
输出：9
解释：缺失的正整数包括 [1,5,6,8,9,10,12,13,...] 。第 5 个缺失的正整数为 9 。

• 示例 2：

输入：arr = [1,2,3,4], k = 2
输出：6
解释：缺失的正整数包括 [5,6,7,...] 。第 2 个缺失的正整数为 6 。

解题思路

思路 1：模拟

1. 核心思想

从 $1$ 开始递增枚举正整数，用指针 $i$ 遍历数组。如果当前整数等于 $arr[i]$，则 $i$ 后移。否则当前整数缺失，$k$ 减 $1$。当 $k = 0$ 时返回当前整数。

2. 具体步骤

第 1 步：$i = 0$，$cur = 1$。

第 2 步：循环直到 $k = 0$：

• 如果 $i < n$ 且 $arr[i] == cur$：$i++$。
• 否则：$k--$，如果 $k == 0$ 返回 $cur$。
• $cur++$。

3. 举例说明

以 $arr = [2, 3, 4, 7, 11], k = 5$ 为例：

• $cur=1$：缺失（$arr[0]=2 \neq 1$），$k=4$。
• $cur=2$：匹配 $arr[0]$，$i=1$。
• $cur=3$：匹配 $arr[1]$，$i=2$。
• $cur=4$：匹配 $arr[2]$，$i=3$。
• $cur=5$：缺失，$k=3$。
• $cur=6$：缺失，$k=2$。
• $cur=7$：匹配 $arr[3]$，$i=4$。
• $cur=8$：缺失，$k=1$。
• $cur=9$：缺失，$k=0$，返回 $9$。

思路 1：代码

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        i, cur = 0, 1
        while k > 0:
            if i < len(arr) and arr[i] == cur:
                i += 1
            else:
                k -= 1
                if k == 0:
                    return cur
            cur += 1
        return -1

思路 1：复杂度分析

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

---

思路 2：二分查找（进阶）

1. 核心思想

$arr[i-1]$ 之前缺失的正整数个数为 $arr[i-1] - i$（因为前 $i$ 个数中，理想情况下连续正整数为 $1,2,\dots,i$，实际为 $arr[0..i-1]$，缺失数 = $arr[i-1] - i$）。

用二分查找找到第一个缺失数 $\ge k$ 的位置。

2. 具体步骤

二分查找最小的 $i$ 使得 $arr[i] - (i+1) \ge k$。

最终缺失的第 $k$ 个数 = $i + k$。

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        l, r = 0, len(arr)
        while l < r:
            mid = (l + r) // 2
            if arr[mid] - mid - 1 >= k:
                r = mid
            else:
                l = mid + 1
        return l + k

思路 2：复杂度分析

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