LeetCode 剑指 Offer 53 - II. 0～n-1中缺失的数字
题目描述
题意分析
数组升序排列、没有重复元素，并且只缺少一个数。为与代码中的数组长度对应，记
m = nums.length，那么完整的数值范围就是 $[0,m]$，共 $m+1$ 个数，要求找出其中未出现在数组里的那个。
解法：二分查找第一个错位下标
核心思路
[!blue]
设缺失值为 $k$。在它之前没有数字缺失，所以 $i<k$ 时有
nums[i] == i；从它之后开始，元素都向左挪了一位，所以 $i\ge k$ 时有nums[i] == i + 1。因此，“值是否等于下标”先成立、后不成立，缺失值就是这两个区间的分界，可以二分查找。用闭区间
[left, right]保存缺失值的候选范围，初始为[0, m]。若nums[mid] == mid，说明缺失值还在中点之后，令left = mid + 1；否则中点已经错位，缺失值在中点或它之前，令right = mid。两种更新都保留了答案，又排除了不可能的一半。当缺失的是 $m$ 时，所有实际元素都与下标对齐，答案仍要落在虚拟位置 $m$，所以初始右端不能只取最后一个下标。循环只在
left < right时取下中点，此时mid < right <= m，绝不会读取nums[m]。每轮候选区间都会缩小，直到
left == right，唯一剩下的位置就是缺失值。缺失 0 时边界不断向左收缩，缺失 $m$ 时不断向右移动，都不需要特殊分支。
解题步骤
- 候选答案区间设为
[0,m]。- 中点对齐则排除到中点，左端取中点加一。
- 错位则保留中点，右端收至中点。
- 返回最终边界下标。
代码实现
class Solution {
public int missingNumber(int[] nums) {
// 长度位置也可作为缺失值，实际中点不会访问这个虚拟位置
int left = 0;
int 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
}
复杂度分析
- 时间复杂度：$O(\log(m+1))$，逐轮折半。
- 空间复杂度：$O(1)$，二分边界。
关键点总结
[!green]
- 数组长度也可能是缺失值，不能排除。
- 返回分界本身，不访问对应元素。
- 数组有序、无重复且只缺一项，才保证每个元素与下标之差只会从 0 变为 1。
易错点总结
[!yellow]
- 右端只取最后下标，会漏掉缺失末尾。
- 错位时丢掉中点，可能跳过最早错位处。
- 返回
nums[left]会错一位或越界。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1060. 有序数组中的缺失元素 | 中等 | 都二分第一个缺失计数达到目标的位置；本题用 nums[i] - i 表示从零开始的缺失量，该题改为相对首项的缺失量并查询第 k 个。 |
| 1539. 第 k 个缺失的正整数 | 简单 | 都利用有序数组中实际值与应有位置之差形成单调缺失计数；该题再按 k 定位边界并补上剩余缺失量。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！