/**
1. 修改次数最少 -> 每个数都改到中位数 ?  为啥是中位数而不是平均值?
1. nums[0 ~ n-1] 都改变成 x, 并且修改次数最小 -> 
    |num[0] - x| + |nums[1] - x| + ... + |nums[n-1] - x| 的值最小 -> x 到数轴上每个点的距离最小 -> x 为中位数
*/

class Solution {
    public int minMoves2(int[] nums) {
        int mid = 0;
        int n = nums.length;
        Arrays.sort(nums);
        if (n % 2 == 0) mid = (nums[n/2] + nums[n/2-1]) / 2;
        else mid = nums[n/2];

        int res = 0;
        for (int i= 0; i < nums.length; i++)
            res += Math.abs(nums[i] - mid);

        return res;
    }
}