题干

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;
    }
};