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: 

1
2
3
4
5
6
7
8
9
10
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]

思路

将问题简化成最简单的两种元素的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def minMoves(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        #Decrease the problem into only two elements.
        #Find the required steps are (maxelement-minelement)
        #Then add up to three elements, add up and make the minimum element
        #equal to the maximum element, then the problem decrease to the 2-element problem
        nums.sort()
        length = len(nums)
        result = 0
        for i in range(length-1,0,-1):
            result += nums[i] - nums[0]
        return result