原文链接: https://leetcode-cn.com/problems/minimum-moves-to-equal-array-elements

英文原文

Given an integer array nums of size n, return the minimum number of moves required to make all array elements equal.

In one move, you can increment n - 1 elements of the array by 1.

 

Example 1:

Input: nums = [1,2,3]
Output: 3
Explanation: Only three moves are needed (remember each move increments two elements):
[1,2,3]  =>  [2,3,3]  =>  [3,4,3]  =>  [4,4,4]

Example 2:

Input: nums = [1,1,1]
Output: 0

 

Constraints:

• n == nums.length
• 1 <= nums.length <= 105
• -109 <= nums[i] <= 109
• The answer is guaranteed to fit in a 32-bit integer.

中文题目

给你一个长度为 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 <= 105
• -109 <= nums[i] <= 109
• 答案保证符合 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)$

---

最后

如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ (“▔□▔)/

也欢迎你 关注我（公主号后台回复「送书」即可参与长期看题解学算法送实体书活动）或 加入「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。

所有题解已经加入 刷题指南，欢迎 star 哦 ~

统计信息

通过次数	提交次数	AC比率
56783	92868	61.1%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
最少移动次数使数组元素相等 II	中等