第 k 个缺失的正整数

解题思路：

  1. 缺失个数为 arr[i] -（i + 1）,因为数组下标是从 0 开始的，而元素是从 1 开始的，所以计算个数的时候，除了减掉下标值之外，还需要再减 1；

  2. 找到第一个缺失数大于等于 k 的索引 left（寻找大于等于 k 的区间的左边界），即 arr[i] -（i + 1）< k；

  3. 返回 left + k；

图解：

复杂度：

  1. 时间复杂度： O(logn), n 是数组长度；

  2. 空间复杂度： O(1)；

代码实现：

function findKthPositive(arr: number[], k: number): number {
    // k 小于数组的第一项，说明前 k 个肯定都是缺失的
    if (arr[0] > k) return k;

    let left = 0;
    let right = arr.length - 1;

    // 寻找 arr[mid] - (mid + 1) 大于等于 k 区间的左边界
    while (left <= right) {
        let mid = left + (right - left >> 1);

        if (arr[mid] - (mid + 1) === k) {
            right = mid - 1;
        } else if (arr[mid] - (mid + 1) < k) {
            left = mid + 1;
        } else if (arr[mid] - (mid + 1) > k) {
            right = mid - 1;
        }
    }

    return left + k;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
评论

中午好👏🏻，我是 ✍🏻   疯狂 codding 中...

粽子

这有关于前端开发的技术文档和你分享。

相信你可以在这里找到对你有用的知识和教程。

了解更多

目录

  1. 1. 第 k 个缺失的正整数
  2. 2. 解题思路：
  3. 3. 图解：
  4. 4. 复杂度：
  5. 5. 代码实现：