使数组元素相等的减少操作次数

难度: Medium

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

找出 nums 中的最大值。记这个值为 largest 并取其下标 i （下标从 0 开始计数）。如果有多个元素都是最大值，则取最小的 i 。
找出 nums 中的 下一个最大 值，这个值 严格小于 largest ，记为 nextLargest 。
将 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 * 10⁴
1 <= nums[i] <= 5 * 10⁴

Submission

运行时间: 121 ms

内存: 26.5 MB

class Solution:
    def reductionOperations(self, nums: List[int]) -> int:
        # nums.sort()
        # i, n, diff, ans = 0, len(nums), 0, 0
        # while i < n:
        #     j = i
        #     while j < n and (j == i or nums[j] == nums[j - 1]):
        #         j += 1
        #     ans += diff * (j - i)
        #     diff += 1
        #     i = j
        # return ans

        s = list(set(nums))
        s.sort()
        dt = dict()
        dt.update(zip(s, range(len(s))))

        return sum([dt[x] for x in nums])

Explain

这个题解首先将数组 nums 中的元素去重并排序，得到一个有序的不重复元素数组 s。然后，使用字典 dt 来映射每个元素在 s 中的索引，这个索引实际上表示的是，从最小值到当前值需要经过多少步骤才能使所有元素变得相等。例如，最小的元素映射到 0，表示不需要任何操作，第二小的元素映射到 1，表示需要一步操作使其降低到最小元素的级别，以此类推。最后，通过遍历原始数组 nums，并使用映射 dt 计算总的操作次数。每个元素的操作次数就是它对应的索引值。

时间复杂度: O(n + u log u)

空间复杂度: O(u)

# 创建一个去重后的列表 s 并排序
s = list(set(nums))
s.sort()
# 创建一个字典 dt，用于存放每个元素在 s 中的位置
dt = dict()
dt.update(zip(s, range(len(s))))
# 计算总的操作次数，每个元素的操作次数是它在 s 中的位置
return sum([dt[x] for x in nums])

Explore

在题解中使用去重并排序的数组s是为了简化操作次数的计算。去重是因为重复的元素在计算变化步骤时会被重复计算，而排序是为了确保从最小元素到最大元素的顺序，使得每个元素到最小元素的操作步数能够直接通过它们的索引差计算得出。如果直接在原数组nums上操作，由于可能包含重复元素且无排序，将难以直接确定每个元素到最小值的确切步骤数。

在构建映射字典dt时，每个元素的字典值即其在排序后的数组s中的索引。由于s是升序排序的，索引0对应最小元素，索引1对应第二小的元素，依此类推。这样，每个元素的索引值直接表示了将该元素减小到最小元素所需的操作步数（即从该元素减到比它小的下一个元素，一直到最小元素）。

这个步骤数是通过元素在排序后的数组s中的位置（索引）来确定的。索引表示了从最小元素到当前元素的顺序位置，每增加一的索引值意味着需要额外一个操作步骤来降低该元素至下一级较小的元素。最终，这个索引值就是从该元素减到最小元素所需的总操作步数。

如果nums数组中的所有元素已经相等，去重后的数组s将只包含一个元素，此时该元素的索引为0。构建的映射字典dt将给这个唯一的元素赋值0，表示不需要任何操作。遍历原数组nums时，每个元素的操作次数都是0。因此，尽管算法执行了一些步骤（如去重和排序），但实际的操作次数计算结果是0，没有进行额外的、不必要的操作次数计算。