Given a non-empty integer array, find the minimum number of moves required to make all array elements equal, where a move is incrementing a selected element by 1 or decrementing a selected element by 1.
You may assume the array's length is at most 10,000.
Example:
Input:
[1,2,3]
Output:
2
Explanation:
Only two moves are needed (remember each move increments or decrements one element):
[1,2,3] => [2,2,3] => [2,2,2]
问最少需要多少次操作,能够将数组中所有元素的值修改为一样的(操作是指将数组中的元素加一或者减一)
其实这题就是找到数组的中位数,该中位数就是最终修改成的元素。当然了,这里的中位数不是广义上的中位数,当数组的元素为奇数时,“中位数”是从小到大排列后位于中间的数。如果是偶数的话,“中位数”是两个中间的数之间的任意一个数字。
这里很多人会以为是计算出平均值作为最终元素,其实不然。简单的讲一下为何“中位数”是最终元素的原因。假设有一个长度为n的数组,其中包括元素a1, a2, ... an
,已知该数组已经有序,则可以知道,对于任意一个数字M,它到各个元素的距离和dist为|a[1] - M| + |a[2] - M| + ... + |a[n] - M|
。如果M<a1, 则dist = n * M - sum
, 同理,如果M > a1, 则dist = sum - n * M
。 简单来说,如果M小于最小值或是大于最大值,每个元素都必须走到最小值或最大值之外才能到达M,因此M一定位于[a1, an]之间。
现在开始找M的最佳位置。将M从最小值a1逐步向最大值an移动。假设M=a1+1且M<a2, 此时可以确信的是a1的移动距离增加了1,但是同时an的移动距离减少了1。也就是说,如果M在ai和aj间移动,二者到M的距离和是不变的。但是对于a2,a3...,a[n-1]来说,每个元素的移动距离都减少了1。也就是说,C在不断的向中位数移动的时候,对于整体数组的移动距离和来说是不断减少的。同理,当C到达中位数,并且继续向右移动时,会发现整体数组的移动距离也随之增加。
代码如下:
public int minMoves2(int[] nums) {
Arrays.sort(nums);
int i = 0, j = nums.length - 1, result = 0;
while(i < j) {
result += nums[j--] - nums[i++];
}
return result;
}