LeetCode 462. 最小操作次数使数组元素相等 II
题目描述
题意分析
每次只能把一个元素加
1或减1。若最终都变为整数t，元素x至少需要|x-t|次操作，沿着目标方向调整就能达到这个次数。因此要最小化的是所有元素到同一个目标值的绝对距离之和。
解法：排序取中位数
核心思路
[!blue]
将数组排序，把最小与最大、次小与次大依次配对。对任意一对
a <= b，都有|a-t|+|b-t| >= b-a：目标t落在[a,b]内时，两段距离恰好拼成b-a；落在区间外时还要多走一段往返距离。排序后各对形成的区间相互嵌套，中间位置属于所有这些区间，所以选择中位数能让每一对同时达到最低代价。数组长度为奇数时，剩下的中间元素也无需移动；长度为偶数时，中间两个数之间的任意整数都同时满足所有配对，总代价相同。
因此直接选择
nums[n/2]：奇数长度时是唯一的中间数，偶数长度时是右中位数。再累加所有元素与它的绝对差，就得到了能够实际达到的总下界，也就是最少操作数。
解题步骤
- 排序并选择
nums[n/2]。- 累加每个元素与中位数的绝对差。
- 返回总操作数。
一个元素或全部元素相等时，所有差值都为零。重复值、负数都不影响配对证明。题目保证答案在 32 位整数范围内，且元素范围使单次相减也不会超出该范围；Java 用
long累加后按返回类型转换。
代码实现
class Solution {
public int minMoves2(int[] nums) {
Arrays.sort(nums);
// 中位数同时落在排序后每对首尾元素之间
int median = nums[nums.length / 2];
long moves = 0;
for (int num : nums) {
moves += Math.abs(num - median);
}
return (int) moves;
}
}
import "sort"
func minMoves2(nums []int) int {
sort.Ints(nums)
// 中位数同时落在排序后每对首尾元素之间
median := nums[len(nums)/2]
moves := 0
for _, num := range nums {
if num >= median {
moves += num - median
} else {
moves += median - num
}
}
return moves
}
复杂度分析
- 时间复杂度：$O(n\log(n+1))$，排序主导，求和线性。
- 空间复杂度：求和本身 $O(1)$，另计排序实现的辅助空间。
关键点总结
[!green]
- 配对距离给出全局下界，中位数让所有配对同时达到该下界。
- 偶数长度无需计算两个中位数的平均值，任选其中一个即可。
- 当前实现会对输入数组排序。
易错点总结
[!yellow]
- 不排序就取中间下标，它未必是中位数。
- 平均值并不保证绝对距离和最小，不能直接代替中位数。
- 相减后不取绝对值，正负差会错误抵消。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 453. 最小操作次数使数组元素相等 | 中等 | 原题一次调整n-1个元素，本题只调整一个元素，最优目标从最小值变为中位数。 |
| 296. 最佳的碰头地点 | 困难 | 二维曼哈顿距离可拆为两个一维绝对距离和，每一维都复用中位数最优性。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！