题目描述

数组 arr 中的值符合等差数列的数值规律：在 0 <= i < arr.length - 1 的前提下，arr[i+1] - arr[i] 的值都相等。

然后，我们从数组中删去一个 既不是第一个也不是最后一个的值。

给你一个缺失值的数组，请你帮忙找出那个被删去的数字。

样例

输入：arr = [5,7,11,13]
输出：9
解释：原来的数组是 [5,7,9,11,13]。

输入：arr = [15,13,12]
输出：14
解释：原来的数组是 [15,14,13,12]。

限制

• 3 <= arr.length <= 1000
• 0 <= arr[i] <= 10^5

算法

(暴力枚举) $O(n)$

1. 首先求出 arr[1] - arr[0] 与 arr[n - 1] - arr[n - 2] 的差值 diff1 和 diff2。
2. 如果这两个差值不相等，若 diff1 == 2 * diff2，则缺失的值为 arr[0] + diff2；若 diff2 == 2 * diff1 则缺失的值为 arr[n - 1] - diff1。
3. 如果这两个差值相等，则说明差值就是 diff1（或 diff2），遍历一次数组，找到相邻两个元素不等的时候返回答案。
4. 如果没有找到，说明整个数组值全部相等，则直接返回 arr[0]。

时间复杂度

• 最多遍历一次数组，故时间复杂度为 $O(n)$。

空间复杂度

• 只需常数的额外空间。

C++ 代码

class Solution {
public:
    int missingNumber(vector<int>& arr) {
        int n = arr.size();
        int diff1 = arr[1] - arr[0];
        int diff2 = arr[n - 1] - arr[n - 2];

        if (diff1 != diff2) {
            if (diff1 == 2 * diff2)
                return arr[0] + diff2;
            else
                return arr[n - 1] - diff1;
        }

        for (int i = 1; i < n - 2; i++)
            if (arr[i + 1] - arr[i] != diff1)
                return arr[i] + diff1;


        return arr[0];
    }
};