0%

LeetCode 1539. Kth Missing Positive Number

Posted on In

题目

原题在此
Given an array arr of positive integers sorted in a strictly increasing order, and an integer k.
Find the kth positive integer that is missing from this array.

Example 1:
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.

Example 2:
Input: arr = [1,2,3,4], k = 2
Output: 6
Explanation: The missing positive integers are [5,6,7,…]. The 2nd missing positive integer is 6.

Constraints:

  • 1 <= arr.length <= 1000
  • 1 <= arr[i] <= 1000
  • 1 <= k <= 1000
  • arr[i] < arr[j] for 1 <= i < j <= arr.length

解析

如果是一个没有missing数的数组,此时arr[i] == i + 1.
也就是说在一个missing了一些数的数组中,到下标i为止missing的个数为arr[i] - (i+1).
这个等式对于数组任意下标i都成立,所以可以用二分查找法快速检索.
当循环结束时 l == r,返回 l + k 即可.

代码

1
2
3
4
5
6
7
8
9
10
11
12
func findKthPositive(arr []int, k int) int {
    var l, r, m int = 0, len(arr), 0
	for l < r {
        m = (l + r) / 2
        if(arr[m] - m - 1 < k) {
            l = m + 1
        } else {
            r = m
        }
	}
	return l + k
}