题目大意
给定一个长度为 n 的非空整数数组，找到让数组所有元素相等的最小移动次数。每次移动可以使 n - 1 个元素增加 1。
示例：
输入:
[1,2,3]
输出:
3
解释:
只需要3次移动（注意每次移动会增加两个元素的值）：
[1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]
方法一：暴力法（单步增加）
最直观的思路，动态维护一个最大的数max,每次将除了max之外的数+1。直到最小的数等于最大的数。
public static int minMoves(int[] nums) {
int min = 0, max = nums.length-1;
int moves = 0;
while(true) {
for(int i=0;i<nums.length;i++) {
if(nums[min] > nums[i]) min = i; //更新最小值索引
if(nums[max] < nums[i]) max = i; //更新最大值索引
}
int diff = nums[max]-nums[min];
if(diff==0) break;
for(int i=0;i<nums.length;i++)
if(i!=max) nums[i] += 1;
moves += 1;
}
return moves;
}
注意：
while里面的两次for循环理论上可以合并，但是diff==0 break的时候，需要两次break才能跳出大循环；将for循环拆开写逻辑更加简单。
最简单的方法超时了，其他方法如下。
方法二：暴力法(跳跃增加)
注意到方法一中，我们每次只为n-1个元素增加1，其实可以一次增加diff = max - min，其他的逻辑不变，直到min == max。
public static int minMoves(int[] nums) {
int min = 0, max = nums.length-1;
int moves = 0;
while(true) {
for(int i=0;i<nums.length;i++) {
if(nums[min] > nums[i]) min = i; //更新最小值索引
if(nums[max] < nums[i]) max = i; //更新最大值索引
}
int diff = nums[max]-nums[min];
if(diff==0) break;
for(int i=0;i<nums.length;i++)
if(i!=max) nums[i] += diff;
moves += diff;
}
return moves;
}
方法三：巧用排序
这里我们来看一种更聪明的办法，以[1,2,3,4]为例。我们将原始数组排序，最大的元素排到了末尾，最小的元素在开头。记总共移动的次数为moves.
- 首先计算diff = max-min = 4-1 = 3。要缩小第一次的差值，要进行3次移动,moves+=3.
- 此时，数组变为[4,5,6,4]。最大的数变为nums[n-2] = 6. diff = 6-4 = 2. 所以moves+=2.
- 下一轮，数组变为[6,7,6,6],最大的数变为nums[n-3]....
到这里规律很清楚了，每一次加上diff以后，数组中的最大的值的下标左移一位。在上述演化过程中，我假设数组中n-1个数更新了，但实际上，不管更新与否，diff的差值是不变的。 - 所以实际只维护diff的变化即可。
public int minMoves(int[] nums) {
Arrays.sort(nums);
int cnt = 0;
for(int i = nums.length-1;i>0;--i)
cnt += nums[i]-nums[0];
return cnt;
}
方法四：反向思维
最后这个方法应该是最好理解的解法：每次将n-1个数加一，相当于1个数-1，只要最后所有的数减到与最小的数相等，就达到了题目的要求。
public static int minMoves(int[] nums) {
//Arrays.sort(nums);
//int min = nums[0];
int min = Integer.MAX_VALUE;
for(int i=0;i<nums.length;i++)
min = Math.min(min,nums[i]);
int ans = 0;
for(int i=0;i<nums.length;i++)
ans += nums[i]-min;
return ans;
}
