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

1. 题目简介

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

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

2. 问题分析

让 n - 1 个元素加 1，可以转化成让剩下的那个元素减 1。两种操作得到的数组并不相同，但所有元素之间的差值相同，所以达到“所有元素相等”所需的操作次数也相同。

例如 [1, 2, 3] 中，让后两个元素加 1，得到 [1, 3, 4]。再把整个数组统一减 1，就得到 [0, 2, 3]，相当于只让第一个元素减 1。整体加减同一个数，不会影响元素是否相等。

这样，问题就变成：每次选一个元素减 1，最少多少次能让它们相等？最终值不能大于原数组的最小值 min，因为操作只能减小元素。选得比 min 更小，又会让每个元素多减几次，所以目标取 min 时次数最少。

每个元素需要减少 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;
    }
}

代码先找到 min，再累加每个元素与它的差值。例如 [1, 2, 3] 的差值之和为 0 + 1 + 2 = 3，所以最少需要 3 次操作。

4. 复杂度分析

• 时间复杂度：O(n)，其中 n 为数组 nums 的长度。
• 空间复杂度：O(1)，只保存最小值和累计次数。

来源：Coding 101 原文 · 免费阅读，引用请保留出处。内容使用说明