Leetcode-1551. 使数组中所有元素相等的最小操作数（超简单解法）

链接

1551. 使数组中所有元素相等的最小操作数

题目

存在一个长度为 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

思路

我们先来看几个例子：

• 当n=1，arr = [1]，显然答案为0.
• 当n=2，arr = [1,3]，答案为1，即让1+1,3-1，都往均值2靠。
• 当n=3，arr = [1,3,5],答案为2，即让1+1=2,5-1=4,  2+1=3,4-1=3，所有数都往均值3靠。
• 当n=4，arr = [1,3,5,7]，此时均值为4，所有的数两两一组往4靠，1+3*1,7-3*1,3+1*1,5-1*1，如此所有的数都变成4，而操作次数就是（4-1）+（4-3）=4.

由此我们可以发现规律，无论n为奇数还是偶数，都是让所有数往最中间（均值）靠，且左右两边对称，最左边的数加一次1，最右边的数减一次1，最终所有数都变成均值。操作次数就等于均值依次减去所有均值左边的数求和，或者均值右边的所有数依次减掉均值求和。

拿n=4来说，arr = [1,3,5,7]，均值为4，即（4-1）+（4-3）=4或者（7-4）+（5-4）=4

C++ Code

class Solution {
public:
int minOperations(int n) {
//等差数列 Sn=n*a1+n(n-1)d/2
//总的个数 n
//均值 a1+(n-1)*d/2=1+(n-1)*2/2=n
int ave=n;
int N=0;
for(int i=1;i<ave;i+=2) N+=ave-i;
return N;
}
};

最后

以上就是明理唇彩最近收集整理的关于Leetcode-1551. 使数组中所有元素相等的最小操作数（超简单解法）的全部内容，更多相关Leetcode-1551.内容请搜索靠谱客的其他文章。