453. 最小操作次数使数组元素相等

1. 题目简介

难度：中等，原题链接：453. 最小操作次数使数组元素相等。

给你一个长度为 n 的整数数组，每次操作将会使 n - 1 个元素增加 1 。返回让数组所有元素相等的最小操作次数。

2. 问题分析

这道题在代码上比较简单，重点考察的是对题意的理解。

题目中唯一的操作就是将 n - 1 个元素加 1。考虑长度为 n 的数组 nums，假设除了 nums[0] 之外，其他的元素都加了 1，那么等价于将 nums[0] 减 1。

因此，问题等价于每次将数组中的 1 个元素减 1，直到所有元素相等。

极易求证，要是操作次数最少，则需要将所有数组中所有元素都减少到最小值，即最小操作次数为 sum(nums[i] - min).

3. 代码实现

class Solution {
    public int minMoves(int[] nums) {
        int min = nums[0];
        for (int num: nums) {
            if (num < min) {
                min = num;
            }
        }
        int ans = 0;
        for (int num: nums) {
            ans += num - min;
        }
        return ans;
    }
}

也可以通过遍历一次来实现，实现方式类似 sum(nums) - n * min。区别在于，在 LeetCode 这道题的测试用例中，乘法计算 n * min 让运行时间变得稍微长一点（1ms 与 2ms 的区别）

4. 复杂度分析

• 时间复杂度：O(n)，其中 n 为数组 nums 的长度。
• 空间复杂度：O(1)，没有使用额外的空间。