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.