05 August 2008
给一个整数数组，可以对里面的的n-1个元素同时+1，求让所有元素都相等的最少次数
因为最后每个数都相等设为X，sum是开始数组和，n是数组长度，所以有公式：n*X=sum+(n-1)*k，即求k，一个自然的想法是 递增k，计算sum+(n-1)*k，找到第一个sum+(n-1)*k能被n整数的数，就得到k了。
不过这有问题，实际上sum初始值不同，得到的k也不同，而这种解法得到的k是相同的。
因为每个数都会经历递增的过程，最后达到一个ceiling。假设数组元素最终为X，数组最小元素min需要经过X-min次增长，最大元素max需要经过X-max次增长，(X-min)-(X-max)=max-min就是max不变
其余元素包括min 增长的次数，经过这些次增长后，min元素和max元素大小相等，且它俩成为当前数组最小元素。
然后我们再让这俩最小元素增长到当前数组最大元素（初始数组次最大元素max2）的大小，增长的次数是max2-min，最终使得这三个元素相等。每一次增长都让数组中大小相同的元素增加一个，从1到2到3~~~n，故总共增加了max-min,max2(初始数组次最大元素)-min,max3-min，总和就是sum-min*n
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public int minMoves(int[] nums) {
int min = Integer.MAX_VALUE;
int sum = 0;
for (int n : nums) {
min = Math.min(min, n);
sum += n;
}
return sum - nums.length * min;
}
}