LeetCode 1539. Kth Missing Positive Number

題目:

給定一個array，array 中missing value組成另外一個array，給一個k值，求第k個missing value。見範例。

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.

思路:

1. go through array整個數字，去匹配並尋找所有missing value，找到的時候k就減一，直到k=0
2. num =1 需要一個自然常數遞增
   n = len(arr) array的邊界
3. for i in range(0,n):
   如果一直沒有找到匹配，arr[i]就會保持不變
   while arr[i] != num and k!=0: 在array中還沒有找到匹配的數字，k已經為0的情況
   result = num
   num += 1
   k -=1
4. if k ==0 :
   return result
   else:
   num+=1
5. 整個array go through 完都還沒找到missing value
   result = num -1
   while k >0:
   result +=1
   k-=1

Coding:

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        num=1
        n = len(arr)
        
        for i in range(0,n):
            while arr[i] != num and k != 0:
                result = num
                num +=1
                k-=1
            if k == 0:
                return result
            else:
                num +=1
        result = num -1
        while k >0:
            result +=1
            k-=1
        return result