leetCode 1539. 第 k 个缺失的正整数

1539. 第 k 个缺失的正整数
      给你一个 严格升序排列 的正整数数组 arr 和一个整数 k 。

请你找到这个数组里第 k 个缺失的正整数。

示例 1：

输入：arr = [2,3,4,7,11], k = 5
输出：9
解释：缺失的正整数包括 [1,5,6,8,9,10,12,13,…] 。第 5 个缺失的正整数为 9 。

示例 2：

输入：arr = [1,2,3,4], k = 2
输出：6
解释：缺失的正整数包括 [5,6,7,…] 。第 2 个缺失的正整数为 6 。

一、迭代

由于数组是严格升序排列 的正整数数组，所以是从1开始的，我们可以从头遍历arr数组，记录当前缺失的元素个数，知道找到缺失的元素

/**
 * @param {number[]} arr
 * @param {number} k
 * @return {number}
 */
var findKthPositive = function(arr, k) {
// 记录当前缺失个数	当前pivot 当前下标
    let count = 0, pivot = 1, index = 0
    while(count < k){
        if(pivot == arr[index]){
            index = index + 1 < arr.length ? index + 1 : index
        }else{
            count++
        }

        pivot++
    }
    return pivot - 1;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

二、二分查找

当前位置 缺失元素 arr[i] - i - 1 = 1

我们需要找到第k个缺失的元素，他的排列序列是一个非严格递增的序列，也就是说，可以通过二分查找，找到k的位置

确定一个区间[i,j]，满足lack[i] < k <= lack[j]，则第k个缺失的数为k - (arr[i] - i - 1) + arr[i]，arr[i] - i - 1表示arr[i]位置缺少的元素个数，k - 缺失个数表示从arr[i]开始还缺少几个元素，再加上arr[i]，就是第k个缺失的元素。

/**
 * @param {number[]} arr
 * @param {number} k
 * @return {number}
 */
var findKthPositive = function(arr, k) {
// 如果第一个缺失元素比k大的话，直接返回k
    if(arr[0] > k){
        return k;
    }

// 找到数量大于k的最小位置
    let left = 1, right = arr.length
    while(left < right) {
        const mid = Math.floor(left + (right - left) / 2)
        const x = mid < arr.length ? arr[mid] : 10000
        if(x - mid - 1 >= k){
            right = mid
        }else{
            left = mid + 1;
        }
    }
     // 第k个缺失的数 - （最小位置之前的那个数所缺失的个数） + 最小位置前面的那个数
     // 5 - （7 - 3 - 1） + 7 = 第五个缺失的数 - 7前面有3个缺失的数 + 7
    return k - (arr[left - 1] - (left - 1) - 1) + arr[left - 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
25
26