HackMD
1539.Kth Missing Positive Number
tags: Easy,Array,Binary Search
1539. Kth Missing Positive Number
題目描述
Given an array arr of positive integers sorted in a strictly increasing order, and an integer k.
Return the kth positive integer that is missing from this array.
範例
Example 1:
Input: arr = [2,3,4,7,11], k = 5
Output: 9
Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,...]. The 5th missing positive integer is 9.
Example 2:
Input: arr = [1,2,3,4], k = 2
Output: 6
Explanation: The missing positive integers are [5,6,7,...]. The 2nd missing positive integer is 6.
Constraints:
- 1 <=
arr.length<= 1000 - 1 <=
arr[i]<= 1000 - 1 <=
k<= 1000 arr[i]<arr[j]for 1 <=i<j<=arr.length
Follow up:
Could you solve this problem in less than O(n) complexity?
解答
Python
class Solution:
def findKthPositive(self, arr: List[int], k: int) -> int:
def feasible(mid) -> bool:
return arr[mid] - mid - 1 < k
l, r = 0, len(arr)
while l < r:
mid = l + (r - l) // 2
if feasible(mid):
l = mid + 1
else:
r = mid
return l + k
Ron ChenMon, Mar 6, 2023
Javascript
function findKthPositive(arr, k) {
let left = 0;
let right = arr.length - 1;
let missing = 0;
while (left <= right) {
const mid = ~~((left + right) / 2);
missing = arr[mid] - mid - 1;
if (missing < k) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left + k;
}
學習了，本來還暴力解，不過也是會過ㄎㄎ
MarsgoatMon, Mar 6, 2023
