---

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

• 标签：数组、数学
• 难度：简单

题目链接

• 1228. 等差数列中缺失的数字 - 力扣

题目大意

描述：给定一个由整数组成的等差数列数组 $arr$，原数组是等差的（相邻两项差值相等）。但现在数组中缺失了一个数（不是首项也不是末项），数组长度至少为 $3$。

要求：找出缺失的那个数字。

说明：

• $3 \le arr.length \le 1000$。
• $0 \le arr[i] \le 10^{5}$。

示例：

• 示例 1：

输入：arr = [5,7,11,13]
输出：9
解释：原数组应为 [5,7,9,11,13]，缺失了 9。

• 示例 2：

输入：arr = [15,13,12]
输出：14
解释：原数组应为 [15,14,13,12]，缺失了 14。

解题思路

思路 1：数学公式

1. 核心思想

等差数列有一个重要的性质：如果数组是完整的（没有缺失），则相邻两项的差值为常数 $d$。

本题中缺失的不是首项也不是末项，所以首项和末项都是正确的。由此可以计算出理论上的公差：

$$d = \frac{arr[n-1] - arr[0]}{n}$$

其中 $n$ 是数组的长度（不包括缺失的那个数），但注意题目给的数组已经是缺失了一个数的，所以理论上的数组长度应该是 $n + 1$。所以：

$$d = \frac{arr[n-1] - arr[0]}{n}$$

（$arr[n-1] - arr[0]$ 是实际首尾差，在完整的 $n+1$ 个元素的等差数列中，首尾之间共有 $n$ 个间隔）。

得到公差后，遍历数组，找到相邻两项差值不等于 $d$ 的位置，缺失的数就是 $arr[i] + d$。

2. 具体步骤

第 1 步：计算公差 $d = (arr[n-1] - arr[0]) / n$。

第 2 步：遍历 $i$ 从 $0$ 到 $n-2$，如果 $arr[i+1] - arr[i] \ne d$，返回 $arr[i] + d$。

第 3 步：理论上一定会找到，所以循环外不需要返回值（或者返回 $arr[0]$ 作为兜底）。

3. 结合示例走一遍

$arr = [5,7,11,13]$

$n = 4$，$d = (13 - 5) / 4 = 8 / 4 = 2$

遍历：

• $arr[1] - arr[0] = 7 - 5 = 2 == d$ ✓
• $arr[2] - arr[1] = 11 - 7 = 4 \ne d$ → 缺失的数为 $arr[1] + d = 7 + 2 = 9$

返回 $9$。

思路 1：代码

class Solution:
    def missingNumber(self, arr: List[int]) -> int:
        n = len(arr)
        # 计算理论公差
        d = (arr[-1] - arr[0]) // n
        # 找到差值不等于公差的位置
        for i in range(n - 1):
            if arr[i + 1] - arr[i] != d:
                return arr[i] + d
        # 实际上不会执行到这里
        return arr[0]

思路 1：复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是数组长度。只需一次遍历。
• 空间复杂度：$O(1)$，只需要常数个变量。

思路 2：二分查找

1. 核心思想

由于等差数列是有序的，可以利用二分查找来优化。如果 $arr[i]$ 是正确位置上的数（没有缺失），那么 $arr[i]$ 应该等于 $arr[0] + i \times d$。

如果 $arr[mid]$ 是正确的（$arr[mid] == arr[0] + mid \times d$），说明缺失的数在右半部分；否则在左半部分（包括 $mid$ 位置）。

2. 代码

class Solution:
    def missingNumber(self, arr: List[int]) -> int:
        n = len(arr)
        d = (arr[-1] - arr[0]) // n

        left, right = 0, n - 1
        while left < right:
            mid = (left + right) // 2
            # 如果 arr[mid] 是正确位置上的数
            if arr[mid] == arr[0] + mid * d:
                left = mid + 1
            else:
                right = mid
        # left 是第一个不符合等差数列规律的位置
        return arr[0] + left * d

3. 复杂度分析

• 时间复杂度：$O(\log n)$，二分查找。
• 空间复杂度：$O(1)$。

本题 $n \le 1000$，思路 1 的 $O(n)$ 已经足够快。但如果 $n$ 很大（如 $10^5$），思路 2 的二分优势就更明显。两种思路都很简洁，面试时可以先给出思路 1 再优化到思路 2。