Question

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

English Version

题目描述

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

我们会从该数组中删除一个 既不是第一个 也 不是最后一个的值，得到一个新的数组  arr。

给你这个缺值的数组 arr，返回 _被删除的那个数_ 。

 

示例 1：

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

示例 2：

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

 

提示：

• 3 <= arr.length <= 1000
• 0 <= arr[i] <= 105
• 给定的数组 保证 是一个有效的数组。

解法

方法一：等差数列求和公式

等差数列求和公式为 $\frac{n(a_1 + a_n)}{2}$，其中 $n$ 为等差数列的项数，$a_1$ 为等差数列的首项，$a_n$ 为等差数列的末项。

因为题目中给出的数组是一个等差数列，且缺失了一个数，所以数组的项数为 $n + 1$，首项为 $a_1$，末项为 $a_n$，则数组的和为 $\frac{n + 1}{2}(a_1 + a_n)$。

因此，缺失的数为 $\frac{n + 1}{2}(a_1 + a_n) - \sum_{i = 0}^n a_i$。

时间复杂度 $O(n)$，其中 $n$ 为数组的长度。空间复杂度 $O(1)$。

class Solution:
  def missingNumber(self, arr: List[int]) -> int:
    return (arr[0] + arr[-1]) * (len(arr) + 1) // 2 - sum(arr)

class Solution {
  public int missingNumber(int[] arr) {
    int n = arr.length;
    int x = (arr[0] + arr[n - 1]) * (n + 1) / 2;
    int y = Arrays.stream(arr).sum();
    return x - y;
  }
}

class Solution {
public:
  int missingNumber(vector<int>& arr) {
    int n = arr.size();
    int x = (arr[0] + arr[n - 1]) * (n + 1) / 2;
    int y = accumulate(arr.begin(), arr.end(), 0);
    return x - y;
  }
};

func missingNumber(arr []int) int {
  n := len(arr)
  d := (arr[n-1] - arr[0]) / n
  for i := 1; i < n; i++ {
    if arr[i] != arr[i-1]+d {
      return arr[i-1] + d
    }
  }
  return arr[0]
}

方法二

class Solution:
  def missingNumber(self, arr: List[int]) -> int:
    n = len(arr)
    d = (arr[-1] - arr[0]) // n
    for i in range(1, n):
      if arr[i] != arr[i - 1] + d:
        return arr[i - 1] + d
    return arr[0]

class Solution {
  public int missingNumber(int[] arr) {
    int n = arr.length;
    int d = (arr[n - 1] - arr[0]) / n;
    for (int i = 1; i < n; ++i) {
      if (arr[i] != arr[i - 1] + d) {
        return arr[i - 1] + d;
      }
    }
    return arr[0];
  }
}

class Solution {
public:
  int missingNumber(vector<int>& arr) {
    int n = arr.size();
    int d = (arr[n - 1] - arr[0]) / n;
    for (int i = 1; i < n; ++i)
      if (arr[i] != arr[i - 1] + d) return arr[i - 1] + d;
    return arr[0];
  }
};