跳转至

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

题目描述

给你一个整数数组 nums。

在一步操作中，你可以将任意单个元素 nums[i] 的值 增加 1。

返回使数组中的所有元素都 相等 所需的 最小总操作次数 。

 

示例 1:

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

输出: 3

解释:

使所有元素相等的操作如下:

  • 将 nums[0] = 2 增加 1, 变为 3。
  • 将 nums[1] = 1 增加 1, 变为 2。
  • 将 nums[1] = 2 增加 1, 变为 3。

现在，nums 中的所有元素都等于 3。最小总操作次数为 3。

示例 2:

输入: nums = [4,4,5]

输出: 2

解释:

使所有元素相等的操作如下:

  • 将 nums[0] = 4 增加 1, 变为 5。
  • 将 nums[1] = 4 增加 1, 变为 5。

现在，nums 中的所有元素都等于 5。最小总操作次数为 2。

 

提示:

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 100

解法

方法一： 计算总和与最大值

本题要求将数组中的所有元素变为相等，且每次只能将某个元素增加 1。为了使操作次数最少，我们应当将所有元素都变为数组中的最大值。

因此，我们可以先计算数组的最大值 \(\textit{mx}\) 和数组元素的总和 \(\textit{s}\)，那么将所有元素变为 \(\textit{mx}\) 所需的操作次数即为 \(\textit{mx} \times n - \textit{s}\)，其中 \(n\) 是数组的长度。

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

1
2
3
4
5
6
class Solution:
    def minMoves(self, nums: List[int]) -> int:
        n = len(nums)
        mx = max(nums)
        s = sum(nums)
        return mx * n - s

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

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

1
2
3
4
5
6
7
8
func minMoves(nums []int) int {
    mx, s := 0, 0
    for _, x := range nums {
        mx = max(mx, x)
        s += x
    }
    return mx*len(nums) - s
}

1
2
3
4
5
6
function minMoves(nums: number[]): number {
    const n = nums.length;
    const mx = Math.max(...nums);
    const s = nums.reduce((a, b) => a + b, 0);
    return mx * n - s;
}

评论