LeetCode 题解工作台
第 k 个缺失的正整数
给你一个 严格升序排列 的正整数数组 arr 和一个整数 k 。 请你找到这个数组里第 k 个缺失的正整数。 示例 1： 输入： arr = [2,3,4,7,11], k = 5 输出： 9 解释： 缺失的正整数包括 [1,5,6,8,9,10,12,13,...] 。第 5 个缺失的正整数为 9…
2
题型
4
代码语言
3
相关题
当前训练重点
简单 · 二分·搜索·答案·空间
答案摘要
class Solution: def findKthPositive(self, arr: List[int], k: int) -> int:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·搜索·答案·空间 题型思路
题目描述
给你一个 严格升序排列 的正整数数组 arr 和一个整数 k 。
请你找到这个数组里第 k 个缺失的正整数。
示例 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 <= arr.length <= 10001 <= arr[i] <= 10001 <= k <= 1000- 对于所有
1 <= i < j <= arr.length的i和j满足arr[i] < arr[j]
进阶：
你可以设计一个时间复杂度小于 O(n) 的算法解决此问题吗？
解题思路
方法一：二分查找
class Solution:
def findKthPositive(self, arr: List[int], k: int) -> int:
if arr[0] > k:
return k
left, right = 0, len(arr)
while left < right:
mid = (left + right) >> 1
if arr[mid] - mid - 1 >= k:
right = mid
else:
left = mid + 1
return arr[left - 1] + k - (arr[left - 1] - (left - 1) - 1)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(log n) using binary search over the valid answer space, or O(n) for a linear scan. Space complexity is O(1) since no extra storage is required beyond counters and pointers. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Ask for edge case handling when k exceeds the last array element.
- question_mark
Probe understanding of how to count missing numbers efficiently at each index.
- question_mark
Test whether candidate can implement binary search over a value range, not just array indices.
常见陷阱
外企场景- error
Miscounting missing numbers leading to off-by-one errors.
- error
Failing to handle cases where kth missing number is larger than the array's last element.
- error
Confusing array indices with actual values when computing missing counts.
进阶变体
外企场景- arrow_right_alt
Find the kth missing positive number in an unsorted array, requiring sorting first.
- arrow_right_alt
Return the list of the first k missing positive numbers instead of only the kth.
- arrow_right_alt
Find the kth missing number where array contains duplicates, requiring deduplication.