LeetCode 453. 最小操作次数使数组元素相等
目录
题目描述
题意分析
题目目标：给定一个长度为 n 的数组，每次操作可以把其中 n-1 个元素同时加 1，问最少多少次操作能让所有元素相等。
核心约束：操作的形式很别扭——不是挑一个元素改，而是挑 n-1 个元素一起改。这种「几乎所有元素都动」的操作是强烈的转化信号：既然大家一起涨，那么真正有意义的只是元素之间的相对差距，绝对值涨到多少无关紧要。第二个信号是题目只问次数不问过程，说明不需要构造具体的操作序列，只要能算出总量即可。第三个信号是数据范围：n 最大约 $10^5$，元素值可达 $10^9$，总和会轻易超过 int 上界，累加必须用 64 位。
边界处理：n 可能为 1，此时数组本身就满足条件，答案为 0；数组元素可能全部相同，答案同样为 0；元素可以是负数，最小值不能初始化成 0 或某个假想的下界；求和与min * n这两个中间量都可能超出 32 位范围，但由于题目保证答案落在 int 内，最终结果可以安全转回 int。
解法：转成减法总量
核心思路
一次给
n-1个元素加 1，可以看成先给所有元素加 1，再把未选择的那个元素减 1。整体加 1 不改变元素之间的差值，因此对“最终全部相等”而言，原操作等价于一次把任意一个元素减 1。转换后只能减小元素，公共终点不能高于原数组最小值
\[\sum_i(nums_i-target)\]min。若终点为target，操作数为\[\sum_i nums_i-n\times min\]
target越大，操作数越少，因此最优终点就是min，答案为这同时给出下界与构造：每个元素高于
min的差值都必须消除，逐个减去这些差值又恰好能让数组全部变成min。
解题步骤
- 用数组首元素初始化
min，用 64 位整数初始化sum。- 一次遍历同时更新总和与最小值。
- 计算
sum - min * nums.length并返回。
[1,2,3]的总和为 6、最小值为 1，答案是6-3=3。单元素或所有元素相等时，公式自然得到 0。总和与乘积都要先提升到 64 位；即使最终返回类型是
int，中间计算也可能溢出 32 位。
代码实现
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)$，只维护总和与最小值。
关键点总结
- 给
n-1个元素加一，与给剩余元素减一具有相同的差值变化。- 等价操作只能减小元素，所以最优公共终点是原数组最小值。
- 操作总数就是所有元素相对最小值的差值之和。
- 最小值用真实数组元素初始化；总和和乘积使用 64 位。
易错点总结
- 把终点选成最大值。
[1,1,10]会算出 18，但正确答案是 9。- 用 32 位整数计算总和或
min * n，大输入会在套用公式前溢出。- 把最小值初始化为 0，会依赖输入取值范围的错误假设。
- 累加相邻元素之差只描述局部关系，必须计算每个元素与全局最小值的差。
- 逐次模拟在差值很大时需要近十亿轮，无法通过。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 462. 最小操作次数使数组元素相等 II | 中等 | 操作改为单元素加一或减一，最优终点从最小值变成中位数 |
| 1685. 有序数组中差绝对值之和 | 中等 | 同样计算「到某点的距离总和」，但要对每个位置都求一次，需前缀和加速 |
| 296. 最佳的碰头地点 | 困难 | 二维版的中位数最优点问题，把行列拆开各求一次一维答案 |
| 945. 使数组唯一的最小增量 | 中等 | 目标从「全部相等」换成「互不相同」，需要排序后贪心抬升 |
| 1551. 使数组中所有元素相等的最小操作数 | 中等 | 数组由公式生成且操作是成对增减，答案可直接推出等差求和的闭式 |