标签: 数学
难度: Medium
存在一个长度为 n 的数组 arr ，其中 arr[i] = (2 * i) + 1 （ 0 <= i < n ）。
一次操作中，你可以选出两个下标，记作 x 和 y （ 0 <= x, y < n ）并使 arr[x] 减去 1 、arr[y] 加上 1 （即 arr[x] -=1 且 arr[y] += 1 ）。最终的目标是使数组中的所有元素都 相等 。题目测试用例将会 保证 ：在执行若干步操作后，数组中的所有元素最终可以全部相等。
给你一个整数 n，即数组的长度。请你返回使数组 arr 中所有元素相等所需的 最小操作数 。
示例 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
提示：
1 <= n <= 10^4运行时间: 19 ms
内存: 16.1 MB
class Solution:
def minOperations(self, n: int) -> int:
if n%2==0:
return int(pow(n,2)/4)
else:
return int((pow(n,2)-1)/4)
该题目的解决思路是通过数学方法计算使数组中所有元素相等的最小操作数。首先，给定数组 arr 是由奇数构成，其中 arr[i] = (2*i) + 1。数组的总和是由首项1，末项(2*n - 1)的等差数列和公式计算得出。当n为奇数时，目标值是数组总和除以n的结果；当n为偶数时，目标值同样是数组总和除以n。然后，通过计算达到目标值需要的操作数，发现当n为偶数时，操作数是n的平方除以4；当n为奇数时，操作数是(n的平方减1)除以4。
时间复杂度: O(1)
空间复杂度: O(1)
class Solution:
def minOperations(self, n: int) -> int:
# 检查n的奇偶性
if n % 2 == 0:
# 如果n是偶数，使用n的平方除以4的公式计算
return int(pow(n, 2) / 4)
else:
# 如果n是奇数，使用(n的平方减1)除以4的公式计算
return int((pow(n, 2) - 1) / 4)
当n为偶数时，数组中间的元素就是平均值，而当n为奇数时，中间元素稍微偏离平均值。因此，n为偶数时，操作数为`n^2 / 4`，这是因为每一对相对于中心对称的元素（如数组的第一个和最后一个）都将被调整到中心值，每对的总调整量相同。而n为奇数时，由于中间的元素已经是目标平均值，剩余元素的调整需要稍微更多的操作，因此使用`(n^2 - 1) / 4`来调整，计算中考虑了中心元素不需要变动。
在这个特定问题中，目标值总是一个整数。因为数组是由连续奇数构成的，其总和是一个等差数列的和，这个和可以被n整除。这是由于等差数列和的公式为`(首项 + 末项) * 项数 / 2`，在这里首项和末项分别是1和(2n-1)，项数是n，因此`(1 + (2n-1)) * n / 2 = n^2`，总和除以n等于n，是整数。
操作数是指使得所有数组元素达到目标平均值所需的总操作步数。在这个题目中，操作是指将一个元素值增加或减少以达到目标值，计算总操作步数是通过考虑所有元素与目标平均值之间的差值来实现的。操作数累计了这些差值的绝对值的总和，分配到每一对对称元素上。
等差数列的和可以使用公式计算：`(首项 + 末项) * 项数 / 2`。在本题中，数组由连续的奇数构成，首项是1，末项是`(2n-1)`，项数是n。将这些值代入公式中，得到数组总和为：`(1 + (2n-1)) * n / 2 = n * n = n^2`。这就是数组的总和，也是通过数学公式直接计算得到的结果。