【原】LeetCode 462.最少移动次数使数组元素相等II(中等)

题目描述:

给定一个非空整数数组，找到使所有数组元素相等所需的最小移动数，其中每次移动可将选定的一个元素加1或减1。您可以假设数组的长度最多为10000。

示例:

输入:
[1,2,3]

输出:
2

说明：
只有两个动作是必要的（记得每一步仅可使其中一个元素加1或减1）： 

[1,2,3]  =>  [2,2,3]  =>  [2,2,2]

题目分析:

这道题首先需要分析要如何移动才是最优的，再考虑如何进行移动。一般这种题都是选择一些特殊的数（例如众数、平均数、中位数），这里应该选择中位数，每个元素与中位数距离的和就是最少的移动次数。使用排序算法对数组进行排序，然后求出中位数，遍历整个数组，把它们到中位数的差距累加就是题目要的答案。这里直接使用了 Arrays.sort() 对数组进行排序，当然你也可以使用其他排序算法，例如快速排序。

下面举个例子简单验证取中位数是最优的，这里就不使用数学方法证明了。假设有一个整型数组 [1, 2, 2, 2, 3, 4, 6, 7, 8] ，可以求得其众数为 2 ，平均数约为 3.89 这里取整为 4 ，中位数为 3 。在坐标图中标出这几个点，并画出众数、平均数、中位数直线。移动的次数就是点到直线的距离，可以求得所有点到众数 2 这条直线的距离和为 19 ，到平均数 4 这条直线的距离和为 19 ，到中位数 3 这条直线的距离和为 18 ，可见最短的距离和（也就是最少移动次数）是 18 ，即到所有点到中位数这条直线的距离是最短的。

题解:

执行用时: 3 ms

内存消耗: 39.4 MB

class Solution {
    public int minMoves2(int[] nums) {
        // 排序
        Arrays.sort(nums);
        // 中位数
        int mid = nums[nums.length / 2];
        // 移动次数
        int sum = 0;
        // 遍历整个数组
        for (int i : nums) {
            // 累加每个元素与中位数的差值
            sum += Math.abs(mid - i);
        }
        // 返回最少移动次数
        return sum;
    }
}

题目来源:力扣(LeetCode)