leetcode之使数组中所有元素相等的最小操作数（C++）

参考链接

1. https://leetcode-cn.com/problems/minimum-operations-to-make-array-equal/

题目描述

存在一个长度为 n 的数组 arr &＃xff0c;其中 arr[i] &＃61; (2 * i) &＃43; 1 &＃xff08; 0 <&＃61; i

一次操作中&＃xff0c;你可以选出两个下标&＃xff0c;记作 x 和 y &＃xff08; 0 <&＃61; x, y

给你一个整数 n&＃xff0c;即数组的长度。请你返回使数组 arr 中所有元素相等所需的 最小操作数 。

解题思路

每次操作意味着一个数加1同时另一个数减1&＃xff0c;所以数组所有元素总和不变&＃xff0c;数组所有元素最后都等于平均值。该等差数列的平均值等于n&＃xff0c;接着只需要计算索引为n/2之前的数变为n需要的操作数之和&＃xff0c;因为n/2之前的是加1操作&＃xff0c;n/2之和的是减1操作&＃xff0c;只需要算一种。

如果将上述过程用公式推导&＃xff0c;可以直接得到结果n24\frac{n^{2}}{4}4n2​

代码

常规思路

class Solution {
public:int minOperations(int n) {int res &＃61; 0;for (int i &＃61; 0; i < n / 2; i &＃43;&＃43;){res &＃43;&＃61; n - (2 * i &＃43; 1);}return res;}
};


公式法

class Solution {
public:int minOperations(int n) {return n * n / 4;}
};