LeetCode刷题【462】最少移动次数使数组元素相等 II

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

例如:

输入:
[1,2,3]

输出:
2

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

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

题解

以排序后的数组【1,2,3,3,4,5,6,7,8,9】举例

很明显移动的目标值应该是中位数 ，从最外层开始看，这个移动的目标值应该在 最小值1 和 最大值9 之间，因为如果小于1或者大于9必然会更大。而不管这个值是多少，需要移动的次数应该是 n-1 + 9-n 即 1和9之间的距离。

再往内看一层，2和8的话，同样值在2在8之间，这个区间显然在前面的1-9区间之内，需要移动的次数就是 8到2之间的距离，后面依次同理。

而最后到了最内层，4和5的话，需要的值应该在4和5之间都可以（包含4、5，前面的所有都一样包含边界），而这个范围肯定满足前面的所有范围的要求。即移动一次，在4上面或者5上面。而这个值，具体是4或者5都不影响最终的结果的移动次数。

另外一种情况，最后剩下一个数字，这个就更简单了，这个值就是所有位置上的数字需要移动朝向的值，他自己需要移动0次。

代码：

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