LeetCode 1539. Kth Missing Positive Number
2021-01-27 20:37:04 # leetcode # binary search

Problem

LeetCode 1539. Kth Missing Positive Number

1. 题目简述

给出一个有序数组和一个正整数k，找到第k个缺失的正整数。例如：

Example:

Input: arr = [2,3,4,7,11], k = 5
Output: 9
Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,...]. The 5th missing positive integer is 9.

2. 算法思路

二分查找最重要的是确认好check函数，到底是求上边界还是下边界。搞清楚！！！而且具体题目具体分析。

这道题里，需要注意的点是check函数中，这里的判断条件是小于还是小于等于。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int findKthPositive(int[] arr, int k) {
        if (arr[0] > k) {
            return k;
        }
        
        // arr[index]-index-1就是到当前为止一共缺失的数字。
        // 这里的目的是要找到一个位置i，使得到i为止缺失的数字是小于k的最大的。因此是求右边界
        // 注意，这里不能是小于等于k，如果是等于的话，比如[1,2,5,6,7,8]，找第2个miss的数字，这里二分出来的数字是8。如果刚刚好是等于k的话，我们不知道前面连续的数字有多少个，往前算起来比较麻烦，因此要注意check条件。
        int l = 0, r = arr.length - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (arr[mid] - mid - 1 < k) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        
        return arr[l] + k - (arr[l] - l - 1);
    }
}
Prev
2021-01-27 20:37:04 # leetcode # binary search
Next