LeetCode 453. 最小操作次数使数组元素相等
题目描述
题意分析
每次选择数组中的
n - 1个元素各加 1，求让所有元素最终相等的最少操作次数。只需要返回次数，不必给出操作过程。
解法：转成减法总量
核心思路
[!blue]
一次操作只留下一个元素不变，其余元素加 1。可以把它拆成“全部元素加 1，再让那个未选中元素减 1”。整体加 1 不影响元素之间是否相等，所以忽略整体平移后，每次操作就等价于选择一个元素减 1，操作次数不变。
在等价的减法问题中，元素只能变小，因此最终公共值
target不能大于原数组最小值min。将全部元素降到target，恰好需要 $\sum(nums[i]-target)$ 次操作；target越大，所需次数越少，所以最优选择就是min。因而答案为 $\sum nums[i]-n\cdot min$。这不仅是下界，也可以通过把每个大于最小值的元素逐次减到
min达到。映射回原操作后，同样次数就能让所有元素相等；这里的min是等价减法中的目标，不是原操作最终的公共值。
解题步骤
- 用首元素初始化最小值，以 0 初始化总和。
- 扫描数组，累加
sum并更新最小值。- 返回
sum - min * n。总和和乘积使用 64 位计算，题目保证最终答案在 32 位整数范围内。- 数组原本全相等或只有一个元素时，公式自然得到 0。
代码实现
class Solution {
public int minMoves(int[] nums) {
long sum = 0;
int min = nums[0];
for (int v : nums) {
sum += v;
if (v < min) {
min = v;
}
}
// 平移后的最优目标是原最小值，累计每个元素的下降量。
return (int) (sum - (long) min * nums.length);
}
}
func minMoves(nums []int) int {
var sum int64
minValue := nums[0]
for _, value := range nums {
sum += int64(value)
if value < minValue {
minValue = value
}
}
// 平移后的最优目标是原最小值，累计每个元素的下降量。
return int(sum - int64(minValue)*int64(len(nums)))
}
复杂度分析
- 时间复杂度：$O(n)$，一次扫描。
- 空间复杂度：$O(1)$，只保存总和与最小值。
关键点总结
[!green]
- 整体平移不改变相等目标，只改变公共绝对值。
- 等价减法取原最小值，使总下降量最少。
- 公式直接统计次数，无需执行每次操作。
易错点总结
[!yellow]
- 把等价目标选成最大值：减法操作无法将小元素提高。
- 最小值初始化为零：可能取到数组中不存在的更小值。
- 只累加相邻差：没有统计全部元素到共同目标的差距。
- 把原操作最终公共值说成原最小值：混淆了整体平移前后的两个过程。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 462. 最小操作次数使数组元素相等 II | 中等 | 原题每次单独增减一个元素，目标取中位数；本题增加n-1个等价于减少一个，目标取最小值。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！