LeetCode 剑指 Offer 53 - II. 0～n-1中缺失的数字

Categories:

题目描述
思路分析
1. 解法一：二分查找缺失位置（推荐）
相似题目

题目描述

✅ 剑指 Offer 53 - II. 0～n-1中缺失的数字

思路分析

解法一：二分查找缺失位置（推荐）

核心思路：

在有序数组中，若没有缺失，则 nums[i] == i。

找到第一个 nums[i] != i 的位置，即为缺失的数字。

使用二分查找定位该位置。

复杂度分析：

时间复杂度：O(log n)，其中 n 表示数组长度。

空间复杂度：O(1)。

class Solution {
    public int missingNumber(int[] nums) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == mid) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return left;
    }
}

func missingNumber(nums []int) int {
	left, right := 0, len(nums)-1

	for left <= right {
		mid := left + (right-left)/2
		if nums[mid] == mid {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}

	return left
}

相似题目

题目	难度	考察点
268. 丢失的数字	简单	二分/数学
35. 搜索插入位置	简单	二分查找
704. 二分查找	简单	二分查找
278. 第一个错误的版本	简单	二分查找
153. 寻找旋转排序数组中的最小值	中等	二分查找
34. 在排序数组中查找元素的第一个和最后一个位置	中等	二分查找

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/73524399