LeetCode 1228. 等差数列中缺失的数字

2022-09-05 HGNULB 约 5 分钟

文章信息 6 个分类 2 个标签

分类

题目描述

✅ 1228. 等差数列中缺失的数字

题意分析

原本有一个完整的等差数列，从中间抽掉了一项（题目保证抽掉的不是首项也不是末项），剩下的按原顺序给出。要还原出被抽掉的那个数。

「首末项没被动过」这个保证价值极高：它意味着完整数列的首项就是 arr[0]、末项就是 arr[n-1]，而完整数列的项数一定是 n + 1（n 为给定数组长度），于是公差可以直接算出来，等于总跨度除以 n 段间隔，而且这个除法一定整除。

数组长度上限只有 1000，$O(n)$ 扫一遍完全够用。但题目被归到二分标签下，是因为剩余数组有一条很强的单调性质：缺口之前的每一项都严格等于「首项加下标乘公差」，缺口之后的每一项都恰好比这个期望值多出一个公差。这是一个「前半段全为真、后半段全为假」的布尔序列。

注意公差可以是负数（数列递减），也可以是 0 吗——不行，公差为 0 的话所有项相同，抽掉哪一项都无法分辨，题目也不会给这种输入；但代码不应该依赖「公差为正」这个假设。

边界：缺口紧挨着首项、缺口紧挨着末项、公差为负、数组长度恰好为 3。

解法：二分定位缺失项

核心思路

设当前数组长度为 n。完整等差数列有 n + 1 项，首末项之间恰有 n 个公差，因此真实公差为 diff = (arr[n-1] - arr[0]) / n。不能用相邻差，因为那一对可能正好跨过缺口。

若扩展到公差为 0 的输入，所有项以及缺失值都等于 arr[0]，直接返回即可。完成这个保护后，二分部分只需讨论非零公差，此时缺口之后一定会失配。

若没有缺失，第 i 项应为 expected(i) = arr[0] + i × diff。缺口之前，arr[i] == expected(i)；从缺口位置开始，当前数组中的元素来自完整数列的下一项，因此全部失配。这个“先匹配、后失配”的布尔序列可以二分。

使用左闭右闭的候选区间，维护不变量：第一个失配下标始终位于 [left, right] 中。中点匹配时缺口一定在右侧，令 left = mid + 1；失配时中点仍可能是答案，令 right = mid。

正确性说明：公差由未缺失的首末项唯一确定。二分每次依据单调判定排除不含首个失配点的一半区间，并保留该点；结束时 left == right，它就是缺失项在完整数列中的下标。返回该下标的期望值，恰为被删除的数字。计算期望值时使用 64 位整数，避免乘加溢出。

解题步骤

计算 diff = (arr[n-1] - arr[0]) / n。

若 diff == 0，直接返回 arr[0]。

初始化 left = 0、right = n - 1。

当 left < right 时取中点，计算该位置的期望值。

若实际值等于期望值，令 left = mid + 1；否则令 right = mid。

返回 arr[0] + left × diff。

arr = [5,7,11,13] 时公差为 2，首个失配下标为 2，返回 9。arr = [15,13,12] 时公差为 -1，首个失配下标为 1，返回 14。缺口紧邻首项或末项也分别收敛到 1 或 n - 1。

防御性边界 arr = [5,5,5] 的公差为 0，缺失值仍是 5，保护分支直接返回。

代码实现

class Solution {
    public int missingNumber(int[] arr) {
        int n = arr.length;
        long diff = ((long) arr[n - 1] - arr[0]) / n;
        if (diff == 0) {
            return arr[0];
        }

        int left = 0;
        int right = n - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            long expected = arr[0] + (long) mid * diff;
            if (arr[mid] == expected) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return (int) (arr[0] + left * diff);
    }
}

func missingNumber(arr []int) int {
	n := len(arr)
	diff := (int64(arr[n-1]) - int64(arr[0])) / int64(n)
	if diff == 0 {
		return arr[0]
	}

	left, right := 0, n-1
	for left < right {
		mid := left + (right-left)/2
		expected := int64(arr[0]) + int64(mid)*diff
		if int64(arr[mid]) == expected {
			left = mid + 1
		} else {
			right = mid
		}
	}
	return int(int64(arr[0]) + int64(left)*diff)
}

复杂度分析

时间复杂度：$O(\log n)$。每轮将候选区间至少缩小一半。

空间复杂度：$O(1)$。只使用固定数量的整数变量。

关键点总结

完整数列有 n + 1 项，所以首末之间有 n 个间隔，公差分母是 n。

二分对象不是数值大小，而是“当前位置是否仍等于理论值”的单调判定。

失配时必须保留 mid，因此写 right = mid；这与 left < right 的循环模板配套。

公差可为负，分支只比较“相等/不相等”，不要依赖大小方向。

公差为 0 时没有失配边界，应直接返回首项；这也让二分不变量只覆盖严格递增或递减的情形。

易错点总结

公差分母写成 n - 1：arr = [0,2,6] 会算出公差 3 并错误返回 3，正确缺失值是 4。

用前两个元素之差作为公差：arr = [0,4,6] 的首个间隔跨过缺失值 2，会把公差误算成 4。

失配时写 right = mid - 1：arr = [5,7,11,13] 会直接排除真正的缺口下标 2。

匹配时写 left = mid：区间只剩两个位置且中点匹配时，left 不再移动并形成死循环。

返回 arr[left]：同一用例会返回 11；arr[left] 是缺口后的现有元素，答案应返回理论值 9。

按大小决定搜索方向：递减数列 [15,13,12] 会让比较方向反转；使用相等判定才能同时覆盖正负公差。

相似题目

题目	难度	考察点
268. 丢失的数字	简单	无序输入，用求和公式或异或抵消，无法二分
540. 有序数组中的单一元素	中等	判定条件建立在下标奇偶性上，需要按配对关系取中
35. 搜索插入位置	简单	「找第一个不小于目标的位置」模板的最小原型
33. 搜索旋转排序数组	中等	单调性被旋转打断，每轮要先判断哪半边有序