题目描述

给定一个长度为 n 的非空整数数组，找到让数组所有元素相等的最小移动次数。每次移动将会使 n - 1 个元素增加 1。

样例

输入：
[1,2,3]

输出：
3

解释：
只需要3次移动（注意每次移动会增加两个元素的值）：

[1,2,3]  =>  [2,3,3]  =>  [3,4,3]  =>  [4,4,4]

算法

(数学) $O(n)$

1. 每次令 n - 1 个元素的值加 1，相当于对一个元素减 1。
2. 故只需要找到最小的元素值 min_x，让其他大于它的元素减少到 min_x。
3. 具体地，让所有元素的总和 tot 减去 n * min_x。
4. 可以直接使 用C++ STL中的 accumulate 和 min_element 。

时间复杂度

• 求最小值和求和的时间复杂度都是 $O(n)$，故总时间复杂度为 $O(n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    int minMoves(vector<int>& nums) {
        return accumulate(nums.begin(), nums.end(), 0) 
            - nums.size() * *min_element(nums.begin(), nums.end());
    }
};