---
# System prepended metadata

title: Leetcode 539. Kth Missing Positive Number
tags: [Set, Leetcode, Array, Binary Search]

---

## 題解

### Brute force

```python=
class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        # Time complexity: O(n+k)
        # Space compleity: O(1)
        count = 0
        cur = 0
        num = 1
        while count < k:
            if (cur < len(arr) and num != arr[cur]) or cur == len(arr):
                count += 1
            else:
                cur += 1
            num += 1
        return num - 1
```

### Set 比對

```python=
class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        # Time complexity: O(n+k)
        # Space compleity: O(1)
        arr = set(arr)
        num = 1
        while k > 0:
            if num not in arr:
                k -= 1
            num += 1
        return num - 1
```

### K++

1.  缺失的正整数一定 >= k
2.  数组中每出现一个 <= k 的数字, 意味着少了一个缺失的数字, 此时k+1

```python=
class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        # Time complexity: O(n)
        # Space complexity: O(1)
        for num in arr:
            if num <= k:
                k += 1
        return k
```

### 二分搜索

Example: 

```
k = 5
origin: [2,3,4,7,11]
sup:    [1,2,3,4,5]
diff:   [1,1,1,3,6]
```

可以得知 **origin[i] + (k - diff[i]) = ans** => 7 + (5 - 3) = 9 

```python=
class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        # Time complexity: O(logn)
        # Space complexity: O(1)
        left, right = 0 , len(arr) - 1
        while left <= right:
            mid = (left + right) >> 1
            temp = arr[mid] - mid # 還沒完全搞懂
            if temp <= k:
                left = mid + 1
            else:
                right = mid - 1
        return left + k
```