有一个数组,其中的值符合等差数列的数值规律,也就是说:
在 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] <= 10^5
题解:
方法一:
通过首项末项和总数求得差值,然后遍历一遍,如果差值不对就输出。
class Solution:
def missingNumber(self, arr: List[int]) -> int:
delta = (arr[-1] - arr[0]) // len(arr)
for i in range(1, len(arr)):
if arr[i] - arr[i - 1] != delta:
return arr[i] - delta
方法二:
通过求和公式求出总值,然后减去直接求和的总值,即可得出缺失项。
class Solution:
def missingNumber(self, arr: List[int]) -> int:
return (arr[0] + arr[-1]) * (len(arr) + 1) // 2 - sum(arr)