题目描述

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

示例:

1
2
3
4
5
6
7
8
9
输入:
[1,2,3]

输出:   
3

解释:
只需要3次操作（注意每次操作会增加两个元素的值）：
[1,2,3]  =>  [2,3,3]  =>  [3,4,3]  =>  [4,4,4]

解题思路

  • 思维方式：逆向思维、数学
  • 核心思想：每次操作使n - 1个元素+1， 那么就相当于每次有一个元素-1，直到把所有元素都减小到最小值就可以了

代码

1
2
3
4
5
6
7
8
int32_t MinMoves(std::vector<int32_t> nums) {
    int sum = 0;
    int min_num = std::min_element(nums.begin(), nums.end());
    for (const auto& num : nums) {
        sum += num - min_num;
    }
    return sum;
}
  • 时间复杂度：O(n)