[LeetCode] 1539. Kth Missing Positive Number

- Problem

1539. Kth Missing Positive Number

- 내 풀이 1 (hash, brute-force)

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        arr = set(arr)
        num = 0

        while k:
            num += 1
            if num not in arr:
                k -= 1
        
        return num

• 시간 복잡도: O(N)
• 공간 복잡도: O(N)

- 결과 1

- 내 풀이 2 (Binary search)

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        left, right = 0, len(arr) - 1

        while left <= right:
            mid = (left + right) // 2

            if arr[mid] - mid <= k:
                left = mid + 1
            else:
                right = mid - 1
        
        return left + k

• 시간 복잡도: O(logN)
• 공간 복잡도: O(1)

- 결과 2