题干
leetcode 453. Minimum Moves to Equal Array Elements 三种语言解
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个元素,需要自增m次,原来的最小值为min,数字一样后数组的值均为x
sum+m*(n-1)=n*x
另外,发现最小的数min一定自增了m次,因为每次自增时只自增n-1个数,剩下不自增的数一定是当前数组中最大的,而原数组中最小的数在过程结束前都一定不是最大的
所以
min+m=x
将x带入第一个式子得
m=sum-min * n
(盗一个图)
代码
java
class Solution {
public int minMoves(int[] nums) {
int n=nums.length;
int min=nums[0];
int sum=0;
for(int x:nums){
if(x<min)min=x;
sum+=x;
}
return sum-min*n;
}
}
python(是不是很简洁!也很美)
class Solution:
def minMoves(self, nums):
return sum(nums)-min(nums)*len(nums)
C++
class Solution {
public:
int minMoves(vector<int>& nums) {
int sum=0;
int min=nums[0];
int n=nums.size();
for(int x:nums){
if(min>x)min=x;
sum+=x;
}
return sum-n*min;
}
};