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

65 阅读 0 评论 43 点赞

我是靠谱客的博主明理唇彩，最近开发中收集的这篇文章主要介绍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;
}
};