1539. Kth Missing Positive Number

Loading...LeetCode

一边遍历一边记录已经 miss 了多少个正整数（或者干脆记录还有多少个正整数要miss），等超过k时倒着往回扣即可。可能遍历完 array 都没有 miss 足够多，那就要直接再往后数。

Python

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        prev = 1 # previous positive integer
        for n in arr:
            k -= (n-prev) # how many ones missed
            if k <= 0:
                return n+k-1
            prev = n+1
        return arr[-1]+k

Java

class Solution {
    public int findKthPositive(int[] arr, int k) {
        int prev = 1;
        for (int i :arr) {
            k = k - (i-prev);
            if (k<=0) {
                return i+k-1;
            }
            prev = i+1;
        }
        return arr[arr.length-1]+k;
    }
}