1539. Kth Missing Positive Number

Enumerate

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int findKthPositive(int[] arr, int k) {
        int x = 1; // x 为下一个判断的数字
        for (int num : arr) {
            while (x != num) {
                // 存在缺失数字，开始抵消 k
                if (--k == 0) {
                    return x;
                }
                x++;
            }
            x++;
        }

        return x + k - 1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int findKthPositive(int[] arr, int k) {
        // 期望：[1, 2, 3, 4, 5]
        // 实际：[1, 3, 7, 8, 9], k = 4, 缺失：[2, 4, 5, 6]
        // 搜索缺失数字的右侧数字，如：7

        int i = 0, j = arr.length - 1;

        while (i <= j) {
            int midIndex = (i + j) >>> 1;
            int expectedValue = midIndex + 1;

            int missCount = arr[midIndex] - expectedValue;
            if (missCount < k) {
                i = midIndex + 1;
            } else {
                j = midIndex - 1;
            }
        }

        // now: j, i
        return j + 1 + k;
    }
}

References

1539. Kth Missing Positive Number