1539.Kth Missing Positive Number

tags: `Easy`,`Array`,`Binary Search`

題目描述

Given an array arr of positive integers sorted in a strictly increasing order, and an integer k.

Return the k^th 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

Reference

回到題目列表