## 題解

### Brute force

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 比對

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

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

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