给定一个大小为n的非空整数数组，找出使所有数组元素相等所需的最小移动数，其中移动将n-1元素增加1_给定一个大小为n(1≤n≤1000000)且无序的整型数组,数组中可能存在相同元素,请找出

题干

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

python(是不是很简洁！也很美)

class Solution:
    def minMoves(self, nums):
        return sum(nums)-min(nums)*len(nums)          
1
2
3

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13