LeetCode 462 - 最小操作次数使数组元素相等 II

文章目录

• • 摘要
  • 描述
  • 题解答案
  • 题解代码分析
  • • 为什么不是平均数？
    • 中位数为什么是最优解？
    • 为什么偶数个元素也没问题？
  • Swift 可运行 Demo 代码
  • 代码逐步解析
  • 示例测试及结果
  • 与实际场景结合
  • 时间复杂度
  • 空间复杂度
  • 总结

摘要

这道题看起来像个“数学题”，但其实更准确地说，它是一个非常典型的工程决策问题：

当你可以自由地调整每个元素，目标是让整体成本最低时，应该把大家“拉”到哪里？

很多人第一反应是“取平均数”，但这道题偏偏不是。
真正的答案，其实和一个我们经常忽略、但非常重要的概念有关：中位数。

描述

题目给你一个整数数组nums，你可以做的操作非常简单：

• 每一次操作

  • 让某一个元素+1
  • 或者-1

你的目标只有一个：

用最少的操作次数，让数组里的所有元素变得完全一样。

注意几个隐含信息：

• 每次操作只影响一个元素
• 每次只加 1 或减 1
• 最终大家要“对齐”到同一个值
• 数组长度最多 10 万，值的范围很大

题解答案

这道题的结论非常明确，而且值得你记住：

把所有元素调整到数组的中位数，操作次数最少。

具体做法就是：

1. 对数组排序
2. 取中位数
3. 累加所有元素到中位数的绝对差

题解代码分析

为什么不是平均数？

我们先从直觉入手。

很多人会想：

“让大家都变成平均数，整体差距不是最小吗？”

但这里有一个坑：
平均数并不一定是整数，而且即使是整数，也不一定最优。

举个简单的例子：

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

和题目示例完全一致。

与实际场景结合

这道题在真实工程里，其实非常常见，只是你可能没意识到。

几个典型场景：

1. 负载均衡

   • 把请求量调整到一个“最省整体迁移成本”的点

2. 数据校准

   • 传感器读数对齐，减少整体修正代价

3. 日志时间修正

   • 把时间戳统一到一个参考值

4. 费用对齐

   • 多人分摊成本时，调整到“最公平、最少改动”的值

这些问题，本质上都是：

在一维数轴上，找到一个点，使得到所有点的总距离最小。

答案，几乎永远都是：中位数。

时间复杂度

O(n log n)

• 排序占主要时间
• 后续遍历是 O(n)

空间复杂度

O(n)

排序使用了额外数组空间（Swift 的sorted()）。

如果需要极致优化，可以用原地排序或快速选择算法。

总结

这道题非常适合用来建立一个重要直觉：

平均数解决的是“平方误差最小”，中位数解决的是“绝对误差最小”。

一旦你把这个区分记牢：

• 这道题基本就是秒解
• 很多“看起来像数学题”的工程问题，也会变得异常清晰