0～n-1中缺失的数字

解题思路：

  1. 0～n-1 会缺失一个数字，会出现 nums[i] 大于等于 i 的情况，永远不会出现 nums[i] 小于 i 的情况；

  2. 可以看成是寻找满足 nums[i] 等于 i 的区间的右边界；

  3. 若没有丢失的数字，left 会一直 +1，最后 left 等于 nums.length；

  4. 若有丢失的数字，会收缩右边界，直到 right < left 跳出循环；

  5. 最后返回结果 left 即可；

复杂度：

  1. 时间复杂度：O(logn)；

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

代码实现：

function missingNumber(nums: number[]): number {
    let left = 0;
    let right = nums.length - 1;

    //  寻找 nums[mid] 大于等于 mid 的右边界
    while (left <= right) {
        let mid = left + (right - left >> 1);

        if (nums[mid] === mid) {
            left = mid + 1;
        } else if (nums[mid] < mid) {
            // 这种情况永远不会出现
        } else if (nums[mid] > mid) {
            right = mid - 1;
        }
    }

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

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

粽子

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

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

了解更多

目录

  1. 1. 0～n-1中缺失的数字
  2. 2. 解题思路：
  3. 3. 复杂度：
  4. 4. 代码实现：