Kth Missing Positive Number

找第k个missing positive number.

这个题如果没想, 直接做, 会被corners case卡一下, 当k大于(arr[n – 1] – n)的时候, 也就是答案在数组的右边空白的时候, 这个情况下是个定值, 应该是鸽子洞理论的, arr[n-1](数组最大值) – n(数组长度) < k (空位个数) 这个情况.

比如, arr = [1, 3], k = 5, 如果不知道上面这个结论, 可以通过数学推演. 即在(3)的位置上看, 左边只有一个1, 那么有一个空位,数学表示就是arr[n – 1] – n == 1, 这时候问的是k = 5,. 那么需要在3后边补上k – (arr[n-1]-n)个数, 这个数的大小是多大? 是arr[n-1] + k – (arr[n-1] – n) = k + n.

class Solution {
    public int findKthPositive(int[] arr, int k) {
        int n = arr.length;
        if (k > arr[n-1] - n)
            return k + n;
        int[] count = new int[1001];
        for(int i : arr){
            count[i]++;
        }
        int c = 0;
        for(int i = 1; i < 1001; i++) {
            if(count[i] == 0){
                c++;
            }
            if(c == k)
                return i;
        }
        return -2;
    }
}