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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
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; } } |