1.将每次n-1个数+1,转化为每次最大的数-1
public int minMoves(int[] nums) {
/*
看了看答案 ,很巧妙,最后的结果肯定是把数组元素都加到一个相同的值,
也就是每次把n-1个比较小的值+1,这样我们可以转化为每次把最大的数-1
直到减到最小值
*/
int min = Integer.MAX_VALUE;
int sum = 0;
for (int i = 0; i < nums.length; i++) {
sum+=nums[i];
min = Math.min(min,nums[i]);
}
return sum-min*nums.length;
}
2.问题的关键是最后的相同值是多少。将数组调整到相同值最快的方法是:将中位数当做相同值。
public int minMoves2(int[] nums) {
//取中位数为目标值,画图就明白了,当个数是奇数的时候,中位数作为目标值,这样移动的肯定最少,因为关于目标值对称的两个数的移动步数之和是固定的,取中间的数作为目标值时,中间的数就不用移动了。如果是偶数,那么取两个偶数中间的任意一个数都一样。两种情况都是关于中位数对称两数的差值之和
int res = 0;
Arrays.sort(nums);
int i = 0,j = nums.length-1;
while(i<j)
{
res += nums[j] - nums[i];
i++;
j--;
}
return res;
}