462. 最少移动次数使数组元素相等 II

大家好，我是 @负雪明烛。点击右上方的「+关注」↗，优质题解不间断！

题目大意

每次移动，可以将数组中的某一个数字加 $1$ 或者减 $1$。求最少移动多少次，能让数组中的数字都相等。

解题方法

分析

假设经过移动以后，所有的数字最终都等于 。

那么这个 的取值有两种情况：在数组取值范围外、在数组取值范围内。

我们分情况讨论。

情况一：在数组取值范围外

在数组外的含义是或者 。

以 ，为例，说明为什么 不能在数组之外。

因此，一定在 的最小值和最大值之间。

情况二：%22%20aria-hidden%3D%22true%22%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-74%22%20x%3D%220%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-61%22%20x%3D%22361%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-72%22%20x%3D%22891%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-67%22%20x%3D%221342%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-65%22%20x%3D%221823%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%20%3Cuse%20xlink%3Ahref%3D%22%23E1-MJMATHI-74%22%20x%3D%222289%22%20y%3D%220%22%3E%3C%2Fuse%3E%0A%3C%2Fg%3E%0A%3C%2Fsvg%3E#card=math&code=target&id=rTVNy) 在数组取值范围内

当 在数组取值范围内，那么无论 $target$ 选择何值，对于数组的最小值和最大值而言，它们移动到 的次数之和一定是固定的！都等于 。

当我们考虑去除 的最大值和最小值后的「子数组」时，我们发现 不能选择「子数组」范围之外的数字。因为「情况一」中已经证明了，这样的选择不是最优。

综上， 必须是不断选择 数组（以及子数组）最大值和最小值之间的数字。

对于数组 而言，一定选择 或者 。取两者任何一个，结果是相同的。

当数组长度为奇数时，一定选择中位数。

求中位数

如何求中位数？

最简单的方法是将数组 排序，然后取中间的位置的数字。时间复杂度是 。

当然这也是个经典的 问题，可以参考 215. 数组中的第K个最大元素 这题的做法。比如「
基于快速排序的选择方法」，可以把时间复杂度降到 。

囿于时间和篇幅问题，我这里不详细解释了。

代码一：排序

1. 先排序
2. 再取中位数
3. 计算将所有数字移动到中位数需要移动多少次，并累加

class Solution(object):
    def minMoves2(self, nums):
        nums.sort()
        return sum([nums[~i] - nums[i] for i in range(len(nums) / 2)])

class Solution {
    public:
    int minMoves2(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        const int N = nums.size();
        int mid = nums[N / 2];
        int res = 0;
        for (int n : nums) {
            res += abs(n - mid);
        }
        return res;
    }
};

复杂度

• 时间复杂度：。
• 空间复杂度：$O(1)$。

代码二：快速选择

可以参考官方题解的做法。

我这里直接使用 C++ 已经实现的 nth_element()函数。

希望读者在评论区中补充哦！

class Solution {
public:
    int minMoves2(vector<int>& nums) {
        const int N = nums.size();
        int mi = N / 2;
        nth_element(nums.begin(), nums.begin() + mi, nums.end());
        int res = 0;
        for (int n : nums) {
            res += abs(n - nums[mi]);
        }
        return res;
    }
};

复杂度

• 时间复杂度：。
• 空间复杂度：。

  总结

1. 本题的重点是为什么要选择中位数。
2. 计算 也是经典问题，也需要掌握哦！

我是 @负雪明烛 ，刷算法题 1000 多道，写了 1000 多篇算法题解，收获阅读量 300 万。
关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。

• 在刷题的时候，如果你不知道该怎么刷题，可以看 LeetCode 应该怎么刷？
• 如果你觉得题目太多，想在短时间内快速提高，可以看 LeetCode 最经典的 100 道题。
• 送你一份刷题的代码模板：【LeetCode】代码模板，刷题必会
• 我写的 1000 道 LeetCode 题解，都在这里了，免费拿走。