每日leetcode

1539. 第 k 个缺失的正整数 - 力扣（LeetCode）

题目

给你一个 严格升序排列 的正整数数组 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.length <= 1000

• 1 <= arr[i] <= 1000

• 1 <= k <= 1000

• 对于所有 1 <= i < j <= arr.length 的 i 和 j 满足 arr[i] < arr[j] 

进阶：

你可以设计一个时间复杂度小于 O(n) 的算法解决此问题吗？

思路

1. 这题用二分查找也是确实比较合理。
2. 我们可以根据中间点的下标和其存的数据的大小关系来判断往哪个方向探索。
3. 先考虑下标和数据的关系，数据只可能大于或者等于下标+1，那么我们可以利用数据-下标来判断它之前有多少缺的，目标是找到目标数字相邻的存在节点，再去推断该数字是什么。
4. 不妨找大于等于目标数字的最小数据，即arr[x]-x-1==k，如果大于等于k，那么就缩右边界并更新ans，如果小于k，就缩左边界。
5. 如果一直没有更新ans，说明数组内是有序的，那么缺的就是最后一个数据继续加k。
6. 如果有更新ans，那么我们就找到了大于目标数字的最小有效数据，但是他们不一定是相邻的，这里设gap=arr[ans]-ans-1，如果大于k，则说明对应ans前有gap个缺失数字，那么在到达第k个缺失数字前，还有gap-k个多余数字需要减掉，然后再退一步才到目标数字。

代码实现

class Solution {
public:
    int findKthPositive(vector<int>& arr, int k) {
        int n = arr.size()-1;
        int left = 0, right = n, ans = n+1, gap = 0;
        while(left <= right) {
            int mid = left + (right-left) / 2; // 下标
            gap = arr[mid] - mid - 1;
            if(gap >= k) {
                right = mid - 1;
                ans = mid;  
            } 
            else left = mid + 1;
        }
        if(ans == n+1) return arr[ans-1] + k - gap;
        gap = arr[ans] - ans - 1;
        return arr[ans]-1-(gap-k);
    }
};

复杂度分析

• 时间复杂度：O(logn)。
• 空间复杂度：O(1)。

官方题解

• 官解似乎用的是下界，不过基本思路基本是一致的，就不复现了。