LeetCode 1060. 有序数组中的缺失元素
题目描述
给定一个严格递增的正整数数组 nums 和一个正整数 k，从 nums[0] 开始，按从小到大的顺序找到第 k 个不在数组中的整数，并返回它。
示例 1：
输入：nums = [4,7,9,10], k = 1
输出：5
解释：从 4 开始，缺失的整数依次为 5、6、8、11……，第一个缺失的整数是 5。
示例 2：
输入：nums = [1,2,4], k = 3
输出：6
解释：缺失的整数依次为 3、5、6……，第三个缺失的整数是 6。
提示：
1 <= nums.length <= 5 * 10^41 <= nums[i] <= 10^71 <= k <= 10^8-
nums严格递增。
题意分析
给定严格递增的整数数组，从首元素之后开始按整数顺序寻找不在数组中的数，返回第
k个缺失值。k从一开始计数，答案可以位于两个数组元素之间，也可以超过数组最后一个元素。计数起点由
nums[0]决定，不是固定从正整数一开始。数组中的数都已经存在，不能把某个数组元素本身当成缺失答案。
解法：缺失数量上的二分查找
核心思路
[!blue]
从
nums[0]到nums[i]，如果整数完全连续，共应有nums[i] - nums[0] + 1个值；实际数组在这段内有i + 1个值。因此累计缺失数量为missing(i) = nums[i] - nums[0] - i，无需真的列出缺失整数。数组严格递增，向右走到下一元素时，缺失量增加的是两元素之间的空缺数，不会减少。所以
missing(i)单调不减，可以二分定位第一个累计缺失数量达到k的位置。先检查最后一个元素。如果
missing(n - 1) < k，数组内部的缺失数还不够，剩余答案一定在末尾之后。那里每前进一步都是缺失值，因此答案为nums[n - 1] + k - missing(n - 1)。否则二分第一个满足
missing(p) >= k的位置p。因为missing(0) = 0且k为正，这个位置不会是零，前一位置一定存在，并满足missing(p - 1) < k。第
k个缺失值就在nums[p - 1]和nums[p]之间。前一位置已经累计了missing(p - 1)个缺失值，再从它之后向右走k - missing(p - 1)个整数，就得到答案。即使missing(p)恰好等于k，答案也仍是nums[p]之前的缺失值，而不是已经存在的nums[p]。
解题步骤
- 用公式计算末尾的累计缺失量。
- 若它小于
k，从最后一个元素向后补足剩余缺失数量并返回。- 否则在下标区间中二分：累计缺失量不少于
k时保留中点及左侧，不足时移到中点右侧。- 两边相遇得到第一个达标下标，读取它前一位置的值与累计缺失量。
- 返回前一位置的值加上尚未计满的缺失数量。
代码实现
class Solution {
public int missingElement(int[] nums, int k) {
int n = nums.length;
int missingLast = missing(nums, n - 1);
// 内部缺失不足，剩余答案在最后元素之后。
if (missingLast < k) {
return nums[n - 1] + k - missingLast;
}
int left = 0;
int right = n - 1;
while (left < right) {
int mid = left + (right - left) / 2;
// 达标位置仍可能是第一个，保留中点。
if (missing(nums, mid) >= k) {
right = mid;
} else {
left = mid + 1;
}
}
// 从尚未达到第几项的前一元素向后补缺口。
int before = missing(nums, left - 1);
return nums[left - 1] + k - before;
}
private int missing(int[] nums, int index) {
return nums[index] - nums[0] - index;
}
}
func missingElement(nums []int, k int) int {
n := len(nums)
missing := func(index int) int {
return nums[index] - nums[0] - index
}
missingLast := missing(n - 1)
// 内部缺失不足，剩余答案在最后元素之后。
if missingLast < k {
return nums[n-1] + k - missingLast
}
left, right := 0, n-1
for left < right {
mid := left + (right-left)/2
// 达标位置仍可能是第一个，保留中点。
if missing(mid) >= k {
right = mid
} else {
left = mid + 1
}
}
// 从尚未达到第几项的前一元素向后补缺口。
before := missing(left - 1)
return nums[left-1] + k - before
}
复杂度分析
设数组长度为 $n$。
- 时间复杂度：$O(\log(n+1))$，每次用常数时间计算一个下标的缺失量；答案在末尾之外时直接返回。
- 辅助空间复杂度：$O(1)$，只使用二分边界和若干计数变量。
关键点总结
[!green]
- 连续应有数量减去实际数量，得到可直接计算的累计缺失函数。
- 缺失量单调不减，寻找第一个达到
k的下标，而不是查找一个具体数组值。- 内部答案从达标位置的前一个元素补差，末尾外答案单独还原。
易错点总结
[!yellow]
- 用下标或固定的一作为起点，会忽略题目从
nums[0]开始计数的约定。- 缺失量可能连续相等，二分需要找第一个达标位置，不能命中相等就直接返回下标或数组值。
- 省略末尾之外的分支，会在所有下标都未达到
k时错误定位。- 内部答案要从前一位置补缺口，从达标元素本身继续增加会跳过正确空隙。
- 二分成功下标至少为一依赖
k > 0；这里不能把序号当成零基。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1539. 第 k 个缺失的正整数 | 简单 | 同样二分第k个缺失值，原题缺失范围从正整数1开始，本题以数组首元素为起始基准。 |
| 163. 缺失的区间 | 简单 | 原题输出所有缺失区间，本题利用各区间缺失数量直接定位第k个元素。 |