LeetCode 1551. 使数组中所有元素相等的最小操作数
目录
题目描述
题意分析
数组不是输入给的，而是由公式生成的：长度为
n，第i个元素（下标从 0 开始）等于2 * i + 1，也就是 1、3、5、……、2n - 1这串连续奇数。一次操作要同时选两个下标x和y，把arr[x]减 1、arr[y]加 1。问把所有元素变成相等值最少要多少次操作。操作的形态给出了最强的约束：每次减一个、加一个，数组的总和恒定不变。既然最终所有元素都相等，那个公共值只能是平均数，没有任何选择余地。这串奇数的平均数正好是
n，所以目标状态是「全部变成n」，题目里其实不存在「选哪个目标值」的自由度。另一个信号是加减必须成对发生：一次操作只能把 1 个单位从高处搬到低处（也可以搬反方向，但那只会更糟）。因此答案下界就是「所有比
n大的元素超出的总量」，同时也等于「所有比n小的元素亏欠的总量」，这两个量因总和守恒而必然相等。输入只有一个整数
n，上界是 $10^4$。唯一的输入意味着答案是关于n的一个闭式表达式，连循环都不该需要；而 $10^4$ 的量级提示答案在 $10^7$ 级别，int装得下。边界上
n = 1时数组是[1]，本来就相等，答案是 0；n为奇数时序列中真的存在等于n的中位元素，它一次都不用动，这一点在按奇偶分类推导时必须照顾到。
解法：数学配对求和
核心思路
数组第
i项是2*i+1，总和为 $n^2$。一次操作让一个元素加 1、另一个减 1，总和不变，因此所有元素最终只能等于平均值n。一次操作同时减少 1 份盈余并补足 1 份亏欠，所以最少操作数等于所有小于
n的元素到n的差值之和，不能把盈余和亏欠重复相加。数列关于
n对称：首尾、次首与次尾等配对后的和都为2*n。因此每一份亏欠都有对应盈余，可以通过配对搬运恰好补足，上述下界一定可达。设
left = n/2，严格小于n的项有left个。偶数n=2m时差值是前m个奇数，和为 $m^2$；奇数n=2m+1时差值是2,4,...,2m，和为 $m(m+1)$。两种情况统一为(n/2)*((n+1)/2)。不变量：按对称位置搬运时，每次操作都让总亏欠减少 1，且不会制造新的亏欠。 初始总亏欠由公式给出，归零时所有元素都等于
n，所以公式既是下界也是最优值。
解题步骤
- 计算向下取整的一半
n/2。- 计算向上取整的一半
(n+1)/2。- 返回两者乘积。
n=6时数组为[1,3,5,7,9,11]，低于 6 的亏欠为5+3+1=9，公式得到3*3=9。边界n=1时公式为0*1=0，无需特判。
代码实现
class Solution {
public int minOperations(int n) {
return (n / 2) * ((n + 1) / 2);
}
}
func minOperations(n int) int {
return (n / 2) * ((n + 1) / 2)
}
复杂度分析
- 时间复杂度： $O(1)$。
- 空间复杂度： $O(1)$。
关键点总结
- 总和守恒决定最终值只能是平均数
n。- 一次操作同时消除一份盈余与一份亏欠，答案只计算其中一侧。
- 数列关于
n对称，证明亏欠总量一定可以恰好补足。- 整数表达式
(n/2)*((n+1)/2)统一处理奇偶。
易错点总结
- 盈余和亏欠都计入答案：
n=6会得到 18，正确答案是 9。- 奇偶都写成
(n/2)*(n/2)：n=5会得到 4，正确答案是 6。- 逐次模拟搬运： 操作次数本身可达 $O(n^2)$，没有必要构造数组。
- 把目标值当成可自由选择： 操作保持总和不变，最终公共值由平均数唯一确定。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 453. 最小操作次数使数组元素相等 | 中等 | 操作是「除一个外全部加一」，需先等价转化成「单个减一」 |
| 462. 最小操作次数使数组元素相等 II | 中等 | 目标值不再是平均数而是中位数，考的是绝对值之和的最优点 |
| 1523. 在区间范围内统计奇数数目 | 简单 | 同样靠整数除法的向上取整技巧写出 $O(1)$ 闭式，避免逐个遍历 |
| 1588. 所有奇数长度子数组的和 | 简单 | 从暴力枚举转为按元素统计贡献次数，同属组合计数式的降维 |
| 829. 连续整数求和 | 困难 | 由等差求和公式反解方案数，需要枚举项数并判断整除性 |
| 1013. 将数组分成和相等的三个部分 | 简单 | 同样以总和守恒推出每段的目标值，再一次扫描验证可达 |
| 1228. 等差数列中缺失的数字 | 简单 | 由首尾项与项数反推公差，是等差序列性质的直接应用 |