难度: Easy
给你一个 严格升序排列 的正整数数组 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 <= 10001 <= i < j <= arr.length 的 i 和 j 满足 arr[i] < arr[j] 进阶：
你可以设计一个时间复杂度小于 O(n) 的算法解决此问题吗？
运行时间: 18 ms
内存: 16.1 MB
class Solution:
def findKthPositive(self, arr: List[int], k: int) -> int:
count=1
n=0
for i in arr:
while i!=count:
n+=1
if n==k:
return count
count+=1
count+=1
n+=1
while n!=k:
count+=1
n+=1
return count
该题解采用了一种逐个检查的方法。首先，通过设置一个外部计数器 count 来遍历所有自然数，然后与数组 arr 中的元素进行比较。如果当前的 count 值不在 arr 中，即认为这是一个缺失的正整数，此时增加缺失计数器 n。一旦 n 达到 k，即找到了第 k 个缺失的正整数。如果整个数组都遍历完毕，但是缺失的数还没找完，就继续增加 count，直到找到第 k 个缺失的正整数。
时间复杂度: O(k + n)
空间复杂度: O(1)
class Solution:
def findKthPositive(self, arr: List[int], k: int) -> int:
count = 1 # 用来计数当前应该检查的数字
n = 0 # 记录缺失数字的数量
for i in arr:
while i != count: # 当数组元素与计数器不同步时，说明有缺失
n += 1 # 增加缺失数字计数
if n == k: # 如果缺失数达到 k，返回当前计数值
return count
count += 1 # 继续下一个数字
count += 1 # 数组中的这个数存在，继续下一个数字
# 如果数组遍历完，仍未找到第 k 个缺失的数字
while n != k: # 继续增加 count 直到找到第 k 个
count += 1
n += 1
return count # 返回第 k 个缺失的正整数
在给定数组 [2, 5] 中，算法从 count = 1 开始逐个检查每个自然数。首先发现 1 缺失（因为 count = 1 且 1 不等于 2），此时缺失计数器 n 增加 1。接着 count 增加到 2，发现 2 存在于数组，于是跳过。然后 count 增加到 3，发现 3 缺失（因为 3 不等于 5），n 增加 1。同理，4 也缺失，n 再增加 1。当 n 达到 3 时，此时 count = 4，算法将返回 4 作为第 3 个缺失的正整数。因此，算法能有效处理连续缺失数字的情况。
该方法在处理大数组和大 k 值时依然有效，但效率可能不是最优的。尤其当 arr 的最大值接近 1000 而 k 也很大时，该方法需要遍历大量的数字直到找到第 k 个缺失的正整数，这可能导致较高的时间复杂度。性能优化可以考虑使用二分查找来加速确定缺失的正整数的位置，通过比较每个元素与其索引的差值来估算缺失数字的数量，从而减少需要检查的数字数量。
在遍历完数组后，如果没有找到第 k 个缺失的正整数，这意味着第 k 个缺失的数字大于数组中的任何元素。此时，需要继续递增 count，同时更新缺失计数器 n，直到 n 等于 k。这个额外的 while 循环确保即使在数组元素之后仍可以找到缺失的数字，因为缺失的正整数可能会出现在数组的最大值之后。
在数组元素非常稠密时，特别是当数组几乎包含了所有连续的数字，本算法的性能仍然有效，但不是最优的。以 arr = [1, 2, 3, ..., 999] 和 k = 1 为例，算法需要遍历整个数组，直到 count 达到 1000，并且发现 1000 不在数组中时，才能够返回 1000 作为第一个缺失的正整数。这种情况下，算法的时间复杂度与数组的长度直接相关，因此在极端情况下（如稠密数组），效率较低。