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

2022-09-05 HGNULB 约 4 分钟

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

分类

LeetCode CodeTop 简单未解决会员题 1-2 小米

题目描述

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

题意分析

一个等差数列删除了中间的一项，首项和末项都保留，给定删除后按原顺序排列的数组，求被删除的值。只删除一项，不需要返回它的位置。

公差可能为正、负或零。首末项未被删除这一条件很重要：它们仍然覆盖完整数列的全部间隔，因此可以直接用端点推算真实公差，而不是依赖可能跨过缺口的相邻两项。

解法：二分定位缺失项

核心思路

[!blue]

设剩余数组长度为 n，完整数列原有 n + 1 项，所以首项到末项之间有 n 个等长间隔。公差为 diff = (arr[n - 1] - arr[0]) / n，分母应是 n，不是当前数组相邻间隔的个数 n - 1。

完整数列在下标 i 的理论值是 arr[0] + i * diff。假设缺失位置为 p，在 p 之前，剩余数组位置没有变化，实际值与理论值相同；从 p 开始，每个实际元素都来自完整数列的下一个位置，实际值与理论值恰好相差一个公差。

当公差非零时，“实际值是否等于理论值”的结果就从一段匹配变成一段失配，缺口是首个失配位置。这是可以二分的单调条件，与数列是递增还是递减无关。

比较中点时，如果匹配，缺口一定在它右边，令 left = mid + 1；如果失配，缺口可能就在中点，也可能更靠左，令 right = mid 保留它。首末项都还在，保证非零公差时数组末端已经发生位移，首个失配一定存在。

两边界相遇后，返回该位置的理论值，而不是现有数组值，后者已经是缺口后的下一项。公差为零时所有项相同，匹配状态不会改变，但缺失值仍然确定为首项，因此先直接返回首项。

解题步骤

用首末项差除以剩余长度 n，求出完整数列公差。

公差为零时直接返回首项。

在闭区间 [0, n - 1] 中二分：匹配理论值则排除中点及其左侧，失配则保留中点并向左收缩。

当 left == right 时，返回 arr[0] + left * diff。

代码实现

class Solution {
    public int missingNumber(int[] arr) {
        int n = arr.length;
        // 完整数列有 n+1 项，首末之间是 n 个间隔。
        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)
    // 完整数列有 n+1 项，首末之间是 n 个间隔。
    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+1))$，公差计算为常量时间，每轮二分将缺口候选范围缩小约一半。

空间复杂度：$O(1)$，只保存边界、公差和理论值；使用宽整数处理中间差值与乘法。

关键点总结

[!green]

输入少了一项，完整数列比输入多一个间隔，真实公差的分母是剩余长度。

二分的是理论位置是否匹配，公差正负不改变更新方向。

首个失配对应缺失项的原位置，答案取理论值，零公差单独处理。

易错点总结

[!yellow]

用任意相邻两项之差作为公差，该间隔可能跨过缺口，得到真实公差的两倍。

将端点差除以 n - 1，忽略完整数列比现有数组多一项。

失配后使用 right = mid - 1，可能排除真正的首个失配位置，正确写法是保留中点。

返回 arr[left]，会返回移到缺口位置的现有元素，应计算理论值。

忽略零公差，没有首个失配时仍进行同样搜索，无法用匹配变化解释返回结果。

相似题目

题目	难度	关联与区别
1060. 有序数组中的缺失元素	中等	原题一般有序数组可能缺多个值，本题保证等差，可由端点推出公差并查首个偏离预期的位置。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2022/48719087

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！