文章目录
- 摘要
- 描述
- 题解答案
- 题解代码分析
- 为什么不是平均数？
- 中位数为什么是最优解？
- 为什么偶数个元素也没问题？
- Swift 可运行 Demo 代码
- 代码逐步解析
- 示例测试及结果
- 与实际场景结合
- 时间复杂度
- 空间复杂度
- 总结
摘要
这道题看起来像个“数学题”，但其实更准确地说，它是一个非常典型的工程决策问题：
当你可以自由地调整每个元素，目标是让整体成本最低时，应该把大家“拉”到哪里？
很多人第一反应是“取平均数”，但这道题偏偏不是。
真正的答案，其实和一个我们经常忽略、但非常重要的概念有关：中位数。
描述
题目给你一个整数数组nums，你可以做的操作非常简单：
每一次操作
- 让某一个元素
+1 - 或者
-1
- 让某一个元素
你的目标只有一个：
用最少的操作次数，让数组里的所有元素变得完全一样。
注意几个隐含信息：
- 每次操作只影响一个元素
- 每次只加 1 或减 1
- 最终大家要“对齐”到同一个值
- 数组长度最多 10 万，值的范围很大
题解答案
这道题的结论非常明确，而且值得你记住：
把所有元素调整到数组的中位数，操作次数最少。
具体做法就是：
- 对数组排序
- 取中位数
- 累加所有元素到中位数的绝对差
题解代码分析
为什么不是平均数？
我们先从直觉入手。
很多人会想：
“让大家都变成平均数，整体差距不是最小吗？”
但这里有一个坑：
平均数并不一定是整数，而且即使是整数，也不一定最优。
举个简单的例子：
nums = [1, 2, 10] 平均数 = 4.33如果你强行往 4 或 5 拉，左右两边的代价是不对称的。
中位数为什么是最优解？
这是这道题的核心。
如果你把数组排好序：
a1 <= a2 <= ... <= an当你选择一个目标值x时，总操作次数是：
|a1 - x| + |a2 - x| + ... + |an - x|这个函数在数学上有一个非常重要的性质：
当 x 取中位数时，上式取得最小值
直观理解就是：
- 中位数左边的人，往右拉
- 中位数右边的人，往左拉
- 两边的“拉力”正好平衡
这和“拉一群人站成一排，站到最中间最省力”是一个道理。
为什么偶数个元素也没问题？
如果数组长度是偶数，比如：
[1, 2, 9, 10]中位数其实是一个区间[2, 9]，
你选2、3、…、9，得到的最小操作次数是一样的。
所以实现时，直接选排序后n / 2位置的值即可。
Swift 可运行 Demo 代码
importFoundationclassSolution{funcminMoves2(_nums:[Int])->Int{letsortedNums=nums.sorted()letn=sortedNums.countletmedian=sortedNums[n/2]varmoves=0fornuminsortedNums{moves+=abs(num-median)}returnmoves}}代码逐步解析
letsortedNums=nums.sorted()先排序，这是找到中位数的前提。
时间复杂度主要也花在这一步。
letmedian=sortedNums[n/2]- 奇数长度：正中间
- 偶数长度：取右中位数即可
不需要纠结选哪一个，只要是中位数区间内的值都行。
moves+=abs(num-median)这一步非常直观：
- 每个元素到目标值的距离
- 就是需要的操作次数
示例测试及结果
letsolution=Solution()print(solution.minMoves2([1,2,3]))// 2print(solution.minMoves2([1,10,2,9]))// 16print(solution.minMoves2([1,1,1]))// 0print(solution.minMoves2([1,1000000000]))// 999999999输出结果：
2 16 0 999999999和题目示例完全一致。
与实际场景结合
这道题在真实工程里，其实非常常见，只是你可能没意识到。
几个典型场景：
负载均衡
- 把请求量调整到一个“最省整体迁移成本”的点
数据校准
- 传感器读数对齐，减少整体修正代价
日志时间修正
- 把时间戳统一到一个参考值
费用对齐
- 多人分摊成本时，调整到“最公平、最少改动”的值
这些问题，本质上都是：
在一维数轴上，找到一个点，使得到所有点的总距离最小。
答案，几乎永远都是：中位数。
时间复杂度
O(n log n)- 排序占主要时间
- 后续遍历是 O(n)
空间复杂度
O(n)排序使用了额外数组空间（Swift 的sorted()）。
如果需要极致优化，可以用原地排序或快速选择算法。
总结
这道题非常适合用来建立一个重要直觉：
平均数解决的是“平方误差最小”，中位数解决的是“绝对误差最小”。
一旦你把这个区分记牢：
- 这道题基本就是秒解
- 很多“看起来像数学题”的工程问题，也会变得异常清晰
