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

题目描述

这是 LeetCode 上的 453. 最小操作次数使数组元素相等 ，难度为 简单。

给你一个长度为 n 的整数数组，每次操作将会使 n - 1 个元素增加 1 。

返回让数组所有元素相等的最小操作次数。

示例 1：

输入：nums = [1,2,3]

输出：3

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

示例 2：

输入：nums = [1,1,1]

输出：0

提示：

• n == nums.length
• $1 <= nums.length <= 10^5$
• $-10^9 <= nums[i] <= 10^9$
• 答案保证符合 32-bit 整数

---

数学

为了方便，令原数组 $num$ 的总和为 $sum$，最小值为 $min$，最大值为 $max$，长度为 $n$，真实最小操作次数为 $ans$。

由于每次只能将 $n - 1$ 个元素整体加一，因此在最终的相等状态，整体元素的大小值 $t$ 满足关系 $t \geqslant max$。

我们考虑是否必然可以取到关系式中的等号？

答案是不一定，当且仅当 $num$ 本身有 $n - 1$ 个元素与 $max$ 差值相等，才能取得关系式中的等号。

同时我们知道，$ans$ 与 $t$ 存在一一对应关系：

$$ans = \frac{t * n - sum}{n - 1}$$

要取得最小的 $ans$，其实等价于取得最小的 $t$，但仅靠 $t \geqslant max$ 关系，我们无法直接求得 $ans$。

事实上，我们可以通过值变化来进行分析，凭直觉我们会觉得：在配平整个数组的过程中，当前数组中的最小值会参与到自增过程中。

我们通过「反证法」来证明该猜想的正确性。

假设在配平数组的过程，某次自增操作中，「当前最小值」没有参与到自增当中，那么此时自增的对象是除「当前最小值」以外的其余元素，这时候「当前最小值」与其他元素的差值将会增加 $1$，此时如果将操作换成「包含当前最小值自增」的话，我们是可以将最终值 $t$ 减一的，如果最终值 $t$ 变小的话，那么 $ans$ 也会变小，结果会更好。

因此，如果我们某次自增操作中没有包含「当前最小值」对应的元素的话，我们可以通过调整 $t$ 的大小（减一），来将操作调整为「包含当前最小值进行自增」，同时结果会变好。

到这里就结束了吗？

还没有，因为到这里我们还不能直接与原始最小值 $min$ 结合起来。

我们还需要证明 原始的相对最小值 $min$ 在匹配过程中，可以一直保持自身是当前数组中的「相对最小值」。

这可以通过「归纳法」来证明：

如果在每次自增操作中，都包含「当前最小值」，那么意味着原始最小值与其他元素的「相对大小」关系不会发生改变（因为原始最小值会一直作为「相对最小值」参与到每一次自增当中）得证成立。

至此，我们可以得到 $t$ 和 $min$ 的关系式：

$$t = min + ans$$

代入之前我们得到的关系式可得：

$$ans = \frac{(min + ans) * n - sum}{n - 1}$$

变形整理后可得：

$$ans = sum - min * n$$

代码：

class Solution {
    public int minMoves(int[] nums) {
        int n = nums.length;
        long min = nums[0], sum = 0;
        for (int i : nums) {
            min = Math.min(min, i);
            sum += i;
        }
        return (int)(sum - min * n);
    }
}

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.453 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。