- 标签:数学
- 难度:中等
描述:存在一个长度为
在一次操作中,我们可以选出两个下标,记作
现在给定一个整数
要求:返回使数组
说明:
- 题目测试用例将会保证:在执行若干步操作后,数组中的所有元素最终可以全部相等。
-
$1 \le n \le 10^4$ 。
示例:
- 示例 1:
输入:n = 3
输出:2
解释:arr = [1, 3, 5]
第一次操作选出 x = 2 和 y = 0,使数组变为 [2, 3, 4]
第二次操作继续选出 x = 2 和 y = 0,数组将会变成 [3, 3, 3]
- 示例 2:
输入:n = 6
输出:9
通过观察可以发现,数组中所有元素构成了一个等差数列,为了使所有元素相等,在每一次操作中,尽可能让较小值增大,让较大值减小,直到到达平均值为止,这样才能得到最小操作次数。
在一次操作中,我们可以同时让第
class Solution:
def minOperations(self, n: int) -> int:
ans = 0
for i in range(n // 2):
ans += n - 1 - 2 * i
return ans
- 时间复杂度:$O(n)$。
- 空间复杂度:$O(1)$。
数组前半部分元素变化幅度的计算可以看做是一个等差数列求和,所以我们可以直接根据高斯求和公式求出结果。
class Solution:
def minOperations(self, n: int) -> int:
return n * n // 4
- 时间复杂度:$O(1)$。
- 空间复杂度:$O(1)$。