Description: Given a non-empty integer array of size n, find the minimum number of moves required to make all array elements equal, where a move is incrementing n - 1 elements by 1.
Example:
Input: [1,2,3] Output: 3 Explanation: Only three moves are needed (remember each move increments two elements): [1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]题意:给定一个数组,计算最少经过多少次的移动可以使数组所有元素相等;每一次的移动都会令数组中n-1个元素增1;
解法:我们先定义如下变量:
数组移动前的和:sum数组的长度:n最少移动的次数:t移动后所有的元素均相等,每个元素都等于:x数组移动前的最小值:min我们知道对于min来说,不管移动多少次,他都一直是最小值,因为其他元素也会增加,那么移动m次后,可以得到:
t + m i n = x t + min = x t+min=x
移动t次后,最后得到所有元素的和为t * x;对于移动前来说,增加了t*(n-1),可以得到: s u m + t ∗ ( n − 1 ) = t ∗ x sum + t*(n-1) = t*x sum+t∗(n−1)=t∗x 由以上两个公式可以得到: t = s u m − m i n ∗ n t = sum - min*n t=sum−min∗n
