Medium

题目描述

给你一个整数数组 nums，你的目标是使 nums 中的所有元素相等。要完成一次操作，需要遵循以下步骤：

  1. 找到 nums 中的最大值。设其下标为 i（下标从 0 开始）且值为 largest。如果有多个元素都是最大值，选择最小的 i。
  2. 找到 nums 中严格小于 largest 的第二大值。设其值为 nextLargest。
  3. 将 nums[i] 减少到 nextLargest。

返回使 nums 中的所有元素相等所需的操作次数。

示例 1：

输入：nums = [5,1,3]
输出：3
解释：使 nums 中的所有元素相等需要 3 次操作：
1. largest = 5 在下标 0。nextLargest = 3。将 nums[0] 减少到 3。nums = [3,1,3]。
2. largest = 3 在下标 0。nextLargest = 1。将 nums[0] 减少到 1。nums = [1,1,3]。
3. largest = 3 在下标 2。nextLargest = 1。将 nums[2] 减少到 1。nums = [1,1,1]。

示例 2：

输入：nums = [1,1,1]
输出：0
解释：nums 中的所有元素已经相等。

示例 3：

输入：nums = [1,1,2,2,3]
输出：4
解释：使 nums 中的所有元素相等需要 4 次操作：
1. largest = 3 在下标 4。nextLargest = 2。将 nums[4] 减少到 2。nums = [1,1,2,2,2]。
2. largest = 2 在下标 2。nextLargest = 1。将 nums[2] 减少到 1。nums = [1,1,1,2,2]。
3. largest = 2 在下标 3。nextLargest = 1。将 nums[3] 减少到 1。nums = [1,1,1,1,2]。
4. largest = 2 在下标 4。nextLargest = 1。将 nums[4] 减少到 1。nums = [1,1,1,1,1]。

提示：

  • 1 <= nums.length <= 5 * 10^4
  • 1 <= nums[i] <= 5 * 10^4

解题思路

解题思路

这道题要求计算将数组所有元素变为相等所需的操作次数。关键观察是：所有元素最终都会变成数组中的最小值。

核心思路

  1. 排序优化：先对数组排序，这样可以清晰地看到不同数值的分布情况。

  2. 批量操作：关键insight是相同数值的元素可以一起处理。每次操作时，我们将当前最大值的所有元素都减少到次大值。

  3. 计算操作次数：

    • 从大到小遍历不同的数值
    • 对于每个数值，计算有多少个元素需要从更大的值"降级"到当前值
    • 累加所有操作次数

算法步骤

  1. 对数组进行排序
  2. 从右到左遍历排序后的数组
  3. 当遇到新的（更小的）数值时，计算需要多少次操作将之前所有更大的数值都变为当前值
  4. 累加操作次数

例如：[1,1,2,2,3] 排序后仍为 [1,1,2,2,3]

  • 有1个3需要变成2：1次操作
  • 有3个数(1个原来的3 + 2个原来的2)需要变成1：3次操作
  • 总共4次操作

这种方法避免了模拟每个具体操作，而是直接计算总的操作次数。

代码实现

class Solution {
public:
    int reductionOperations(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int operations = 0;
        int reductions = 0;
        
        for (int i = nums.size() - 1; i > 0; i--) {
            if (nums[i] != nums[i - 1]) {
                reductions++;
            }
            operations += reductions;
        }
        
        return operations;
    }
};

class Solution:
    def reductionOperations(self, nums: List[int]) -> int:
        nums.sort()
        operations = 0
        reductions = 0
        
        for i in range(len(nums) - 1, 0, -1):
            if nums[i] != nums[i - 1]:
                reductions += 1
            operations += reductions
        
        return operations

public class Solution {
    public int ReductionOperations(int[] nums) {
        Array.Sort(nums);
        int operations = 0;
        int reductions = 0;
        
        for (int i = nums.Length - 1; i > 0; i--) {
            if (nums[i] != nums[i - 1]) {
                reductions++;
            }
            operations += reductions;
        }
        
        return operations;
    }
}

var reductionOperations = function(nums) {
    nums.sort((a, b) => a - b);
    let operations = 0;
    let reductions = 0;
    
    for (let i = nums.length - 1; i > 0; i--) {
        if (nums[i] !== nums[i - 1]) {
            reductions++;
        }
        operations += reductions;
    }
    
    return operations;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)主要由排序操作决定，遍历数组为O(n)
空间复杂度O(1)只使用了常量级别的额外空间