class Solution {
public:
int findKthPositive(vector<int>& arr, int k) {
}
};
1539. 第 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：
输入：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) 的算法解决此问题吗？
原站题解
python3 解法, 执行用时: 28 ms, 内存消耗: 13.6 MB, 提交时间: 2020-11-12 21:54:10
class Solution:
def findKthPositive(self, arr: List[int], k: int) -> int:
n = len(arr)
for i in range(n):
if arr[i] -i - 1 >= k: # 第i个位置缺失数的个数
return k+i
return k+n
golang 解法, 执行用时: 4 ms, 内存消耗: 2.9 MB, 提交时间: 2020-11-12 21:54:00
func findKthPositive(arr []int, k int) int {
n := len(arr)
for i :=0; i < n; i++ {
if arr[i] - i - 1 >= k {
return k + i
}
}
return k + n
}