# 1539. Kth Missing Positive Number

{% embed url="<https://leetcode.com/problems/kth-missing-positive-number/>" %}

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

{% tabs %}
{% tab title="Python" %}

```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
```

{% endtab %}

{% tab title="Java" %}

```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;
    }
}
```

{% endtab %}
{% endtabs %}
