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

解法一

设这个数为非递减数列，最终相等时均为，那么最少移动次数满足：

其实就是中学数学中一个非常常见的问题，求多个绝对值式子的最小和。
以的简单情况为例，显然当取得最小值时，需要满足, 此时

回到原始问题，

• 当为偶数时，

当满足时，每个二阶子问题的最小值可以同时达到。

• 当为奇数时，

当满足时，每个二阶子问题和的最小值可以同时达到。

总的来说，将数列的中位数作为，就可以得到的最小值。

class Solution {
    public int minMoves2(int[] nums) {
        int average = 0;
        Arrays.sort(nums);
        int ans = 0;
        for (int i = 0, j = nums.length - 1; i < j; ++i, --j) {
            ans += nums[j] - nums[i];
        }
        return ans;
    }
}