1539.Kth Missing Positive Number
===

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

[1539. Kth Missing Positive Number](https://leetcode.com/problems/kth-missing-positive-number/)

### 題目描述

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

> [name=Ron Chen][time=Mon, 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;
}

> 學習了，本來還暴力解，不過也是會過ㄎㄎ
> [name=Marsgoat][time=Mon, Mar 6, 2023]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)