原文链接: https://leetcode-cn.com/problems/reduction-operations-to-make-the-array-elements-equal

英文原文

Given an integer array nums, your goal is to make all elements in nums equal. To complete one operation, follow these steps:

1. Find the largest value in nums. Let its index be i (0-indexed) and its value be largest. If there are multiple elements with the largest value, pick the smallest i.
2. Find the next largest value in nums strictly smaller than largest. Let its value be nextLargest.
3. Reduce nums[i] to nextLargest.

Return the number of operations to make all elements in nums equal.

 

Example 1:

Input: nums = [5,1,3]
Output: 3
Explanation: It takes 3 operations to make all elements in nums equal:
1. largest = 5 at index 0. nextLargest = 3. Reduce nums[0] to 3. nums = [3,1,3].
2. largest = 3 at index 0. nextLargest = 1. Reduce nums[0] to 1. nums = [1,1,3].
3. largest = 3 at index 2. nextLargest = 1. Reduce nums[2] to 1. nums = [1,1,1].

Example 2:

Input: nums = [1,1,1]
Output: 0
Explanation: All elements in nums are already equal.

Example 3:

Input: nums = [1,1,2,2,3]
Output: 4
Explanation: It takes 4 operations to make all elements in nums equal:
1. largest = 3 at index 4. nextLargest = 2. Reduce nums[4] to 2. nums = [1,1,2,2,2].
2. largest = 2 at index 2. nextLargest = 1. Reduce nums[2] to 1. nums = [1,1,1,2,2].
3. largest = 2 at index 3. nextLargest = 1. Reduce nums[3] to 1. nums = [1,1,1,1,2].
4. largest = 2 at index 4. nextLargest = 1. Reduce nums[4] to 1. nums = [1,1,1,1,1].

 

Constraints:

• 1 <= nums.length <= 5 * 104
• 1 <= nums[i] <= 5 * 104

中文题目

给你一个整数数组 nums ，你的目标是令 nums 中的所有元素相等。完成一次减少操作需要遵照下面的几个步骤：

1. 找出 nums 中的 最大 值。记这个值为 largest 并取其下标 i （下标从 0 开始计数）。如果有多个元素都是最大值，则取最小的 i 。
2. 找出 nums 中的 下一个最大 值，这个值 严格小于 largest ，记为 nextLargest 。
3. 将 nums[i] 减少到 nextLargest 。

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

 

示例 1：

输入：nums = [5,1,3]
输出：3
解释：需要 3 次操作使 nums 中的所有元素相等：
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
解释：需要 4 次操作使 nums 中的所有元素相等：
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 * 104
• 1 <= nums[i] <= 5 * 104

通过代码

高赞题解

方法一：排序

提示 $1$

为了使得 $\textit{nums}$ 中所有元素相等，对于 $\textit{nums}$ 中的任意元素 $x$，在整个过程中它所需的操作次数等于严格小于它的不同值的数量。

提示 $1$ 解释

首先，为了使得 $\textit{nums}$ 中所有元素相等，我们需要将 $\textit{nums}$ 中的任意元素都变为 $\textit{nums}$ 中的最小值。

其次，考虑 $\textit{nums}$ 中的任意元素 $x$，每次操作（如有）只能将它变成严格小于它的元素中的最大值。为了将 $x$ 变为 $\textit{nums}$ 中的最小值，需要的操作次数即为严格小于它的不同值的数量。

思路与算法

我们用 $\textit{cnt}$ 统计每个元素所需的操作次数。根据 **提示 $1$**，$\textit{cnt}$ 等于严格小于每个元素的不同值的数量。为了方便统计，我们将 $\textit{nums}$ 升序排序，并从下标 $1$ 开始顺序遍历（$\textit{nums}[0]$ 一定为最小值故无需操作）。

我们将 $\textit{cnt}$ 的初值设置为 $0$，当遍历至下标 $i$ 时，我们比较 $\textit{nums}[i]$ 与 $\textit{nums}[i-1]$ 的大小关系，并更新 $\textit{cnt}$。此时有两种情况：

• 如果 $\textit{nums}[i] = \textit{nums}[i-1]$，此时 $\textit{nums}[i]$ 的操作次数与 $\textit{nums}[i-1]$ 相同，故 $\textit{cnt}$ 不变；

• 如果 $\textit{nums}[i] > \textit{nums}[i-1]$，此时 $\textit{nums}[i]$ 需要首先变为 $\textit{nums}[i-1]$ 才能进行后续操作，因此我们将 $\textit{cnt}$ 增加 $1$。

在遍历的同时，我们维护数组中每个元素的 $cnt$ 之和。遍历结束后，我们返回该值，即为使数组所有元素相等所需的总操作次数。

代码

[sol1-C++]
class Solution {
public:
    int reductionOperations(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int res = 0;   // 总操作次数
        int cnt = 0;   // 每个元素操作次数
        for (int i = 1; i < n; ++i) {
            if (nums[i] != nums[i-1]){
                ++cnt;
            }
            res += cnt;
        }
        return res;
    }
};

[sol1-Python3]
class Solution:
    def reductionOperations(self, nums: List[int]) -> int:
        nums.sort()
        n = len(nums)
        res = 0   # 总操作次数
        cnt = 0   # 每个元素操作次数
        for i in range(1, n):
            if nums[i] != nums[i-1]:
                cnt += 1
            res += cnt
        return res

复杂度分析

• 时间复杂度：$O(n\log n)$，其中 $n$ 为数组 $\textit{nums}$ 的长度。排序数组的时间复杂度为 $O(n\log n)$，遍历数组维护操作次数与总操作次数的时间复杂度为 $O(n)$。

• 空间复杂度：$O(\log n)$，即为排序的栈空间开销。

统计信息

通过次数	提交次数	AC比率
5363	8290	64.7%

提交历史

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