LeetCode 1551. 使数组中所有元素相等的最小操作数
题目描述
题意分析
给定长度
n，数组第i项固定为2i + 1，下标从零开始。每次操作给某一项加一，同时给另一项减一，求让全部元素相等的最少操作次数。数组由公式确定，不必真的创建。一次操作同时进行一增一减，总和保持不变，因此最终公共值不能随意选取。
解法：数学配对求和
核心思路
[!blue]
前
n个正奇数的和为 $n^2$，共有n项，总和不变意味着最后每项必须等于n。把小于
n的元素所缺的数量加起来，记为总亏欠。一次操作最多为这些位置补一个单位，所以操作数至少等于总亏欠。大于n的总盈余与亏欠相等，每次从一个有盈余的位置转移一单位给缺少的位置，就能恰好用这么多次完成，证明下界可达。首尾对称的两个元素之和为
2n，也可以直接成对将较大值多出的量转给较小值。偶数n = 2k时，较小一半的亏欠依次为2k-1, 2k-3, ..., 1，和为 $k^2$。奇数
n = 2k+1时，中间元素已经等于目标，左半亏欠为2k, 2k-2, ..., 2，和为 $k(k+1)$。两种情况统一为floor(n/2) * ceil(n/2)，直接使用整数除法计算即可。
解题步骤
- 计算向下取整的一半
n / 2。- 计算向上取整的一半
(n + 1) / 2。- 返回两者乘积；
n = 1时自然为零。
代码实现
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)$，无需构造数组或模拟操作。
关键点总结
[!green]
- 总和守恒先确定唯一目标值，随后才计算调整代价。
- 每次转移同时消除一单位亏欠与盈余，只需累计一侧。
- 亏欠下界可通过转移或对称配对达到，因此公式给出最优次数。
易错点总结
[!yellow]
- 累加全部绝对差后直接返回，会把一次转移的两端都计费，答案翻倍。
- 不能自由选择某个原数组元素作为目标，公共值由总和与长度唯一确定。
- 长度为奇数时中间项已经等于目标，不应为它额外计数。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 462. 最小操作次数使数组元素相等 II | 中等 | 原题可单独增减元素并选择中位数目标，本题每次一增一减保持总和，目标由平均值固定。 |
| 453. 最小操作次数使数组元素相等 | 中等 | 原题同时增加n-1项，本题在两项之间转移1，操作定义改变了最优目标与计费方式。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！