LeetCode 剑指 Offer 53 - II. 0～n-1中缺失的数字
目录
题目描述
题意分析
有一个长度为
n - 1的递增排序数组，里面的元素两两不同，取值都落在0到n - 1这个范围里。也就是说这n个数恰好少了一个，要求把这个缺失的数字找出来。
「递增排序」这四个字是本题的全部价值所在。如果去掉它，用求和公式作差、或者把所有元素异或起来，都能在 $O(n)$ 时间内得到答案；正因为数组有序，才有机会做到比 $O(n)$ 更快。面试官问这道题，想听的通常不是求和法，而是「你有没有意识到有序性可以换来对数级复杂度」。
有序 + 元素唯一 + 值域连续，三者合起来给出一个非常整齐的性质：没有缺失时必然
nums[i] == i；一旦缺失的数字排在下标i之前，从i开始就会变成nums[i] == i + 1。于是整个数组被切成了泾渭分明的两段——前一段满足nums[i] == i，后一段满足nums[i] != i，而分界点的下标就是答案。「一个布尔判据把有序数组切成假、真两段，求第一个为真的位置」正是二分查找最标准的应用形态。
边界要盯住两处：缺失的可能是 0，此时整个数组都满足
nums[i] != i，分界点是 0；缺失的也可能是n - 1，此时整个数组都满足nums[i] == i，分界点落在数组末尾之外，答案是数组长度。后者决定了二分的右边界必须能取到nums.length这个「虚拟位置」。
解法：二分查找第一个错位下标
核心思路
若缺失值为
k，则数组具有明确分界：i < k时nums[i] == i，i >= k时nums[i] > i。因此答案就是第一个满足nums[i] != i的下标；若所有下标都对齐，答案是数组长度。这不是普通的「查找某个值」，而是对单调判据做边界二分。把数组长度
n看成一个恒为错位的虚拟位置，维护候选答案闭区间[left, right]，初始为[0, n]：
nums[mid] == mid：缺失值一定在右侧，排除mid，令left = mid + 1。nums[mid] != mid：mid可能就是第一个错位位置，保留它，令right = mid。循环中始终有答案位于
[left, right]。因为left < right时取下中点，所以mid < right <= n，即使right是虚拟位置也不会访问越界。最终区间收缩到一点，left就是缺失数字。正确性可由不变量直接得到：对齐位置及其左侧不可能缺数，可以安全丢弃；错位位置右侧也不可能比它更早错位，只保留左半段不会漏解。每轮区间严格缩小，结束时唯一候选必然是第一个错位下标。
解题步骤
- 令
left = 0、right = nums.length，把缺失末尾的情况包含进来。- 当
left < right时，计算mid = left + (right - left) / 2。- 若
nums[mid] == mid，令left = mid + 1；否则令right = mid。- 循环结束后返回
left，不要返回nums[left]。例如
nums = [0, 1, 3, 4, 5]：初始[left, right] = [0, 5]，mid = 2已错位，将right收到 2；随后mid = 1仍对齐，将left推到 2，最终返回 2。若输入为
[0, 1, 2, 3]，所有真实下标都对齐，left会一路推进到 4。这个例子说明右边界必须初始化为数组长度，而不是最后一个下标。
复杂度分析
- 时间复杂度：$O(\log n)$，每轮排除约一半候选位置。
- 空间复杂度：$O(1)$，只使用三个下标变量。
关键点总结
- 二分的依据是判据
nums[i] != i具有单调性，而不只是数组有序。- 答案可能是数组长度，需要把右侧虚拟位置
n纳入候选区间。right = mid保留可能的首个错位位置；left = mid + 1排除已确认对齐的位置。- 返回的是分界下标，而该下标恰好等于缺失的数值。
易错点总结
- 把
right初始化为nums.length - 1：[0, 1, 2]缺 3 时无法得到数组外的答案。- 错位时写
right = mid - 1：可能直接跳过第一个错位位置，例如[0, 2, 3]会漏掉答案 1。- 对齐时写
left = mid：当只剩两个候选位置时区间可能不再缩小，造成死循环。- 使用
left <= right：它属于另一套闭区间模板，不能与right = mid混用。- 返回
nums[left]：缺失中间时会返回后一个数，缺失末尾时还会越界。
代码实现
class Solution {
public int missingNumber(int[] nums) {
int left = 0, right = nums.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] == mid) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
}
func missingNumber(nums []int) int {
left, right := 0, len(nums)
for left < right {
mid := left + (right-left)/2
if nums[mid] == mid {
left = mid + 1
} else {
right = mid
}
}
return left
}
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 268. 丢失的数字 | 简单 | 同样求缺失值但数组无序，只能用求和或异或做到 $O(n)$，正好反衬有序的价值 |
| 35. 搜索插入位置 | 简单 | 最纯粹的「找第一个不小于目标的位置」，答案同样可能落在数组末尾之外 |
| 278. 第一个错误的版本 | 简单 | 判据由接口给出而非数组比较，最能体现「二分的是单调判据」这一本质 |
| 34. 在排序数组中查找元素的第一个和最后一个位置 | 中等 | 要同时求左右两个边界，需要写两次方向相反的二分 |
| 540. 有序数组中的单一元素 | 中等 | 判据换成「配对下标的奇偶性」，需要先构造出单调性再二分 |
| 162. 寻找峰值 | 中等 | 数组整体无序，靠局部斜率单调保证能二分，是「判据单调」的进阶例子 |
| 704. 二分查找 | 简单 | 查找精确值而非边界，用闭区间模板更自然，可用来对照两种区间写法的差异 |
| 287. 寻找重复数 | 中等 | 值域连续但数组无序且有重复，改为对「值」而不是「下标」二分并统计个数 |
| 剑指 Offer 53 - I. 在排序数组中查找数字 I | 简单 | 同一系列的前一题，用两次边界二分求某个值的出现次数 |
| LCR 070. 有序数组中的单一元素 | 中等 | 与 540 同题，可直接套用本题的左闭右开模板 |