跳转至

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

难度中等

题目描述

给你一个长度为 n 的整数数组 nums。

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

每次操作中，你必须将数组中的 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 整数

解法

方法一：数学

思考

每次把 \(n-1\) 个数加一，等价于把剩下那个数减一，直到全部等于最小值。模拟加一会改动整个数组。

因此答案是每个数减到最小值的次数之和，即 \(\sum \textit{nums} - n\cdot\min(\textit{nums})\)。

一次求最小与总和即可，不必真的执行操作。

我们不妨记数组 \(\textit{nums}\) 的最小值为 \(mi\)，数组的和为 \(s\)，数组的长度为 \(n\)。

假设最小操作次数为 \(k\)，最终数组的所有元素都为 \(x\)，则有：

\[ \begin{aligned} s + (n - 1) \times k &= n \times x \\ x &= mi + k \\ \end{aligned} \]

将第二个式子代入第一个式子，得到：

\[ \begin{aligned} s + (n - 1) \times k &= n \times (mi + k) \\ s + (n - 1) \times k &= n \times mi + n \times k \\ k &= s - n \times mi \\ \end{aligned} \]

因此，最小操作次数为 \(s - n \times mi\)。

\(|\textit{nums}[i]|\) 可达 \(10^9\)，且 \(n\) 可达 \(10^5\)，所以 \(s\) 与 \(n \times mi\) 都可能超出 32 位整数范围，题目则保证二者之差仍在 32 位整数内。求和时使用 64 位整数。

时间复杂度 \(O(n)\)，空间复杂度 \(O(1)\)。其中 \(n\) 为数组的长度。

1
2
3
class Solution:
    def minMoves(self, nums: list[int]) -> int:
        return sum(nums) - min(nums) * len(nums)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
    public int minMoves(int[] nums) {
        long s = 0;
        int mi = nums[0];
        for (int x : nums) {
            s += x;
            mi = Math.min(mi, x);
        }
        return (int) (s - (long) mi * nums.length);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
public:
    int minMoves(vector<int>& nums) {
        long long s = 0;
        int mi = nums[0];
        int n = nums.size();
        for (int x : nums) {
            s += x;
            mi = min(mi, x);
        }
        return (int) (s - 1LL * mi * n);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func minMoves(nums []int) int {
    mi := 1 << 30
    s := 0
    for _, x := range nums {
        s += x
        if x < mi {
            mi = x
        }
    }
    return s - mi*len(nums)
}

1
2
3
4
5
6
7
8
9
function minMoves(nums: number[]): number {
    let mi = 1 << 30;
    let s = 0;
    for (const x of nums) {
        s += x;
        mi = Math.min(mi, x);
    }
    return s - mi * nums.length;
}

1
2
3
4
5
6
7
8
impl Solution {
    pub fn min_moves(nums: Vec<i32>) -> i32 {
        let (s, mi) = nums
            .iter()
            .fold((0i64, i32::MAX), |(s, mi), &x| (s + x as i64, mi.min(x)));
        (s - mi as i64 * nums.len() as i64) as i32
    }
}

评论