[leetcode] [python] Kth Missing Positive Number

Memory Usage: 14.6 MB

---

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

Find the kth 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]for1 <= i < j <= arr.length

---

문제 설명

 

오름차 순으로 정렬된 양의 정수가 저장된 array인 arr와 정수 k가 주어진다.

array에서 빠진 수들 중 K번째 양의 정수를 찾는 문제이다. 

 

Example 1을 보면 arr에서 빠진 수는, [1, 4, 5, 8, 9, 10, 12, 13, ...] 이므로, 5번째 수는 9이다.

Example 2를 보면 arr에 빠진 수는 [5, 6, 7, ... ] 이므로, 2번째 수는 6이다.

 

arr의 길이가 1000까지, arr에 들어갈 수 있는 수에는 1000을 포함한다.

k의 수는 1000까지 가능하므로, 최대 2000의 수까지 저장한다. 

ex. arr에 1부터 1000까지 들어가며, k로 1000번째 수를 요구하는 경우, 그 값은 2000이다.

 

 

문제 풀이

 

두 가지 방법으로 문제를 풀었다.

range 특성상 입력된 값은 미포함하므로, +1을 한다.

 

 

1. set으로 만들고, 여집합 연산을 수행하여 k 번째 값 구하기.

k가 1000일 때를 고려하여 다 집어 넣고, 차집합을 구한다. 

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        s = set([i for i in range(arr[-1] + 1001)])
        a = list(s - set(arr))
        return a[k]

84 / 84 test cases passed.

Status: Accepted

Runtime: 56 ms

Memory Usage: 14.6 MB

 

2.  for문을 돌려가며, 1씩 수를 증가시켜 arr에 포함여부를 판단. 미포함한다면 list에 넣기. 

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        answer = []
        for i in range(arr[-1]+1001):
            if i not in arr:
                answer.append(i)
        return answer[k]

84 / 84 test cases passed.

Status: Accepted

Runtime: 292 ms

Memory Usage:14.6 MB