Leetcode 453 Minimum Moves to Equal Array Elements

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，问提升多少次才能使所有数相同，做这种题就一定要动笔写下来

思路：
我们首先来对一个简单点的任意有序数组进行分析，如[a,b,c]，如何使它最后全变成相等呢，首先要明白最后相等的那个数是一定不可能小于c的，所以我们不妨先将a,变成c，即提升c-a次，此时数组为 [c,b+c-a,c],那么显然此时只要将0，2两个位置同时提升b-a即可，故最后答案为b+c-2a

如果是4个数呢？
[a,b,c,d] 先提升d-a，
[d,b+d-a,c+d-a,d] 提升b-a
[d+b-a,b+d-a,c+b+d-2a,d+b-a] 提升c-a即可
故最后答案为 b+c+d-3a = a+b+c+d - 4a
综合这些规律我们可以发现答案就为 sum(nums) - min(nums) * len(nums)

class Solution(object):
    def minMoves(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        return sum(nums) - min(nums)*len(nums)


84 / 84 test cases passed.
difficulty: easy
Runtime: 68 ms