给你一个 严格升序排列 的正整数数组 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 <= 1000
1 <= arr[i] <= 1000
1 <= k <= 1000
- 对于所有
1 <= i < j <= arr.length
的i
和j
满足arr[i] < arr[j]
进阶:
你可以设计一个时间复杂度小于 O(n) 的算法解决此问题吗?
第一种思路:
线性遍历每一个数字看它在不在 arr 里,比较麻瓜没有实现。
时间复杂度:O(K + N)
空间复杂度:O(N)
第二种思路:
比较有趣,利用到了二分的方法。
对于一个 arr[i] 来说,它左边的缺失正整数的数量 n 应该是 = arr[i] - (i + 1)。
我们通过判断 n 和 k 的关系,就可以不断缩减一半的区间。
当二分循环结束的时候,我们应该有 left = right + 1,此时要输出的答案 res 满足 arr[right] < res < arr[left],
假设 arr[right] 之前没有正整数缺失,我们直接返回 arr[right] + k 即可,
但是现在如果考虑它之前有缺失的情况,我们需要返回的就是 arr[right] + (k - (arr[right] - (right + 1))) = k + (right + 1) = k + left。
这个返回值的计算非常巧妙。
时间复杂度:O(logn)
空间复杂度:O(1)
class Solution:
def findKthPositive(self, arr: List[int], k: int) -> int:
# the num of missing positive num before arr[i] =
# arr[i] - (i + 1)
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
n = arr[mid] - (mid + 1)
if n < k:
left = mid + 1
else:
right = mid - 1
# right = left + 1
# arr[right] < res < arr[left]
# before arr[right], we have missing positive num = arr[right] - (right + 1)
# if that is 0, then we return arr[right] + k
# if that part is not 0, we have to eliminate that from k
# return arr[right] + (k - arr[right] - (right + 1))
return left + k
标签:arr,right,正整数,Python,复杂度,缺失,LeetCode,1539,left
From: https://blog.csdn.net/qq_32424059/article/details/141654928