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

2023-04-28 HGNULB 约 8 分钟

文章信息 7 个分类 3 个标签

分类

题目描述

✅ 462. 最小操作次数使数组元素相等 II

题意分析

每次操作可以把任意一个元素加一或减一，问最少多少次操作能让所有元素变得相等。

由于加减都允许且每次只动一个单位，把某个元素从 a 调到目标值 t 所需的操作数恰好是 |a - t|。于是总代价是 $\sum_i nums_i - t $，问题被完全改写成一个纯粹的数学最优化：选一个实数 t，使所有元素到它的绝对距离之和最小。

注意目标值不必是数组里已有的元素，题目也没有要求它是——但下面会看到，最优解总能取在数组中的某个元素上。

数组长度可达 10^5，元素取值范围是完整 int 且可以为负。长度 10^5 意味着不能对候选目标值逐个枚举再求和（那是 $O(n^2)$）；值域跨满 int 意味着距离总和可能达到 10^5 × 4×10^9 量级，远超 int，累加变量必须用 64 位。

边界包括：数组只有一个元素时答案为 0；所有元素已经相等时答案为 0；长度为偶数时中间有两个候选，需要确认它们是否给出相同答案。

解法：排序取中位数

核心思路

暴力做法是枚举每个元素作为目标值，各算一遍距离和取最小，$O(n^2)$。它能过小数据但在 10^5 下是 10^10 次操作。瓶颈在于我们没有利用「距离和关于 t 的变化规律」这一结构。

考察代价函数 $g(t) = \sum_i nums_i - t $ 如何随 t 变化。把 t 向右移动一个微小量 d：所有小于 t 的元素与 t 的距离各增加 d，所有大于 t 的元素各减少 d。设左侧有 L 个、右侧有 R 个，那么总代价的变化量是 $(L - R) \cdot d$。

于是结论立刻浮现：当 L < R（右边元素更多）时右移能降低代价，当 L > R 时左移能降低代价，只有当左右个数平衡时才不能再改进。这个平衡点正是中位数。同时这也说明 $g(t)$ 是分段线性的凸函数——斜率 L - R 随 t 增大而单调不减，因此局部最优即全局最优。

具体到实现：把数组排序后取 nums[n / 2] 作为目标值。n 为奇数时这是唯一的中位数；n 为偶数时它是中间两个数中偏右的那个。偶数情形下，中间两数之间的任意取值（含两端）给出的代价完全相同——因为在这个区间内左右各有 n/2 个元素，斜率恒为 0，函数是一条水平线段。所以取 nums[n/2] 或 nums[n/2 - 1] 都对，不必纠结。

不变量很简单：排序后 nums[n/2] 左侧（含自身）至少有 $\lceil n/2 \rceil$ 个元素、右侧至少有 $\lfloor n/2 \rfloor$ 个元素，这保证了它落在使斜率变号的那个位置上。

确定目标值后，答案就是一次线性扫描累加绝对差。

解题步骤

先对数组排序。之所以必须排序，是因为「中位数」的定义依赖顺序统计量，而排序是最直接的获取方式；虽然理论上可以用快速选择在 $O(n)$ 期望时间内找到中位数，但排序写法更短且在面试中同样被接受。

取 median = nums[n / 2]。之所以用整除而不做奇偶判断，是因为偶数长度下中间两数之间的代价恒定，随便取哪一个都给出同一个最小值，多写一个分支只会增加出错面。

用 64 位变量累加所有 |num - median|。之所以必须用 64 位，是因为 10^5 个元素每个的绝对差可达 4×10^9 量级，总和轻易突破 int 上界；Java 里累加变量声明为 long，Go 的 int 在 64 位平台上本身就是 64 位。

累加完成后转回题目要求的返回类型。之所以这次截断是安全的，是因为题目数据保证最终答案落在 int 范围内。

Go 版本用显式的大小分支代替绝对值函数。之所以这么写，是因为标准库的 math.Abs 只接受浮点数，对整数使用会引入不必要的类型转换和精度顾虑，手写分支既准确又省事。

以 nums = [1, 10, 2, 9] 走一遍，n = 4。排序后是 [1, 2, 9, 10]，median = nums[4 / 2] = nums[2] = 9。

累加：|1 - 9| = 8，|2 - 9| = 7，|9 - 9| = 0，|10 - 9| = 1，总计 16。返回 16。

验证偶数情形下另一个候选是否等价：取 nums[1] = 2 作为目标，|1-2| + |2-2| + |9-2| + |10-2| = 1 + 0 + 7 + 8 = 16，完全相同。再取中间任意值比如 5：4 + 3 + 4 + 5 = 16，仍相同，印证了「中间区间内代价恒定」的结论。而取区间外的值比如 11：10 + 9 + 2 + 1 = 22，明显更差。

再以奇数长度 nums = [1, 2, 3] 走一遍：排序后不变，median = nums[1] = 2，累加 1 + 0 + 1 = 2。若改取 1，则是 0 + 1 + 2 = 3；改取 3，则是 2 + 1 + 0 = 3，都比 2 差，说明中位数确实是唯一最优。

代码实现

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;
    }
}

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)$，凭据是排序是唯一的非线性步骤，随后的取中位数是 $O(1)$、累加是一次 $O(n)$ 扫描；若把排序换成快速选择求中位数，可以降到期望 $O(n)$。

空间复杂度：$O(\log n)$，凭据是累加只用了一个标量，额外开销全部来自排序的递归栈——Java 对基本类型用双轴快排、Go 用 pdqsort，两者的栈深都是 $O(\log n)$；若不允许修改原数组，则需额外 $O(n)$ 拷贝一份。

关键点总结

看到「每次改变一个单位、求最少操作次数」要立刻把它翻译成距离之和，把操作计数问题变成数学最优化问题，后续所有推理都在数学层面进行。

最小化绝对差之和取中位数、最小化平方差之和取平均数，这是一对必须背下来的结论；它们的区别源于绝对值函数的导数是符号函数（只看左右个数）而平方函数的导数是线性的（要看具体数值）。

证明方式比结论更值得掌握：把目标值微移，观察代价变化量为「左侧个数减右侧个数」乘以位移，立刻看出平衡点最优且函数是凸的。这个「微扰法」能迁移到大量最优选址问题。

偶数长度时中间两数之间的任意取值代价相同，所以不需要奇偶特判，nums[n/2] 一律可用——少一个分支就少一处出错。

累加距离时必须用 64 位，这是由「元素数量 × 值域跨度」决定的正确性要求，不是防御性习惯。

面试视角：面试官会先让你写出朴素枚举，然后问「有没有更快的」。答题时不要直接甩出「取中位数」这个结论，而要给出微扰法的推导，这才是面试官想听的。常见追问有两个：一是「能否做到 $O(n)$」，答快速选择；二是「如果代价是平方和呢」，答取平均值并说明推导方式的差异。

易错点总结

累加变量用 int：用例 nums = [-2147483648, 2147483647]，两者绝对差约 4.3×10^9，单次累加就溢出成负数，返回值完全错误。

用平均值作为目标：用例 nums = [1, 10, 2, 9]，平均值是 5.5，取整为 5 时代价是 4 + 3 + 4 + 5 = 16 恰好相同；但换成 nums = [1, 1, 1, 100]，平均值 25.75 取 26 得 25 + 25 + 25 + 74 = 149，而中位数 1 只需 0 + 0 + 0 + 99 = 99。

忘记排序直接取 nums[n / 2]：用例 nums = [1, 10, 2, 9]，未排序时 nums[2] = 2，代价是 1 + 8 + 0 + 7 = 16 侥幸相同；换成 nums = [100, 1, 1, 1] 则取到 nums[2] = 1 也对，但 nums = [1, 100, 1, 1] 取到 nums[2] = 1，而 nums = [1, 1, 100, 1] 取到 100，代价变成 99 + 99 + 0 + 99 = 297 而非 99。

偶数长度时取 nums[n / 2 - 1] 和 nums[n / 2] 的平均并四舍五入：用例 nums = [1, 2, 9, 10]，平均是 5.5 取 6 得 5 + 4 + 3 + 4 = 16 恰好相同，但引入了浮点运算和取整方向的额外风险，直接取 nums[n/2] 更稳。

枚举每个元素作为目标值再取最小：用例长度 10^5 的数组，需要 10^10 次操作，直接超时。

用 Math.abs(num - median) 时两个操作数都是 int：用例 num = Integer.MIN_VALUE、median = 1，减法先溢出再取绝对值，结果为负；本题因数据范围保证不会触发，但把 median 提升为 long 参与减法更安全。

认为目标值必须是数组中的元素而在偶数情形下强行只试 nums[n/2] 之外还额外遍历所有元素比较：用例任意输入，答案正确但退化成 $O(n^2)$，白白丢掉了中位数结论带来的加速。

排序后取 nums[(n - 1) / 2] 并认为它与 nums[n / 2] 在偶数时结果不同而写分支择优：用例 nums = [1, 2, 9, 10]，两者分别是 2 和 9，代价都是 16，多写的比较分支纯属冗余且容易在奇数长度上取错下标。

Go 里用 math.Abs(float64(num - median))：用例元素绝对值超过 $2^{53}$ 的场景（本题受 int32 限制不会触发，但同类题目会），浮点转换丢失精度，累加结果偏差。

空数组不做保护直接访问 nums[n / 2]：用例 nums = []，抛数组越界异常；本题保证数组非空，但在工程代码里这是必须补上的一行。

相似题目

题目	难度	考察点
453. 最小操作次数使数组元素相等	中等	操作变成「给 n-1 个元素加一」，等价于把一个元素减一，答案与最小值相关
296. 最佳的碰头地点	困难	二维网格上的曼哈顿距离最小化，行列独立后各取一次中位数
215. 数组中的第K个最大元素	中等	求顺序统计量本身，考察快速选择，可用来把本题优化到线性
912. 排序数组	中等	手写排序算法，是本题排序步骤的底层实现