题目描述

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，那么实际就是让选定的那一个数减少1了，比如上例中的[1, 2, 3] => [1, 1, 3] => [1, 1, 2] => [1, 1, 1]。既然想要知道让数组元素全部相等的最小移动次数，那么就是所有元素与最小元素的差的和了。

Python

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

Java

public class Solution {
    public int minMoves(int[] nums) {
        int sum = 0;
        int min = Integer.MAX_VALUE;
        for (int num : nums) {
            sum += num;
            if (num < min) {
                min = num;
            }
        }
        return sum - min * nums.length;
    }
}

C++

class Solution {
public:
    int minMoves(vector<int> &nums) {
        int sum = 0;
        int min = INT32_MAX;
        for (int num : nums) {
            sum += num;
            if (num < min) {
                min = num;
            }
        }
        return sum - min * nums.size();
    }
};