代码拉取完成,页面将自动刷新
同步操作将从 doocs/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
在某个数组 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];
}
};
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。