Leetcode 1887. 使数组元素相等的减少操作次数
题目描述
给定一个整数数组 nums，我们的目标是令 nums 中的所有元素相等。每次减少操作需要遵循以下步骤：
- 找出
nums中的最大值，记为largest，并找到它的下标i（下标从0开始计数）。 - 如果最大值有多个，选择下标最小的那个。
- 找到
nums中严格小于largest的下一个最大值，记为nextLargest。 - 将
nums[i]减少到nextLargest。 - 重复这些步骤直到
nums中的所有元素都相等。
要求返回使 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^41 <= nums[i] <= 5 * 10^4
解题思路
思路
要解决这个问题，核心思想是通过找出最大值并依次将它们减少为下一个较小的值，直到所有元素都变成相同的值为止。具体操作步骤如下：
- 统计元素的频次：首先，我们需要统计每个数字在数组中出现的次数。为了方便，可以使用 Python 中的
Counter。 - 排序处理：将所有元素按照大小进行排序，并从大的数字逐步向小的数字做减少操作。
- 计算操作次数：每次减少一个数，记录操作次数。由于每个数会减少到下一个较小的数，因此我们需要计算每个数减少所需要的次数。
代码实现
from collections import Counterclass Solution:def reductionOperations(self, nums: List[int]) -> int:# 统计每个数字出现的次数count = Counter(nums)# 删除最小的键值对，避免后续操作影响del count[min(count.keys())]# 对剩余的键值按键从小到大排序cnt = sorted(count) # 排序只是按照keys()进行排序，返回的是从小到大的排序列表res = 0 # 记录操作次数for i, c in enumerate(cnt):res += (i + 1) * count[c]return res
代码解释
-
Counter(nums)：Counter类用于统计nums中每个元素的出现次数。它返回一个字典，键为数组元素，值为该元素出现的次数。 -
删除最小值：使用
del删除字典中的最小值min(count.keys())。这是为了避免在后续的操作中不必要的元素干扰。 -
排序：通过
sorted(count)将字典中的键按从小到大的顺序排序。排序后的cnt就是从最小到大的所有唯一数字。 -
操作次数计算：遍历
cnt中的每个元素，每次操作会减少当前元素的所有实例。操作次数为该数字的出现次数乘以其在排序中的位置(i + 1)，因为每次减少时都需要减少到一个比当前数字小的数。 -
返回结果：最终，
res存储了所有减少操作的总次数。
时间复杂度分析
- 排序操作：排序的时间复杂度是
O(k log k)，其中k是数组中不同数字的个数。 - 遍历操作：遍历一次
cnt数组的时间复杂度是O(k)，其中k是数组中不同数字的个数。
因此，整体的时间复杂度是 O(k log k)。
空间复杂度
由于我们使用了 Counter 来统计频次，所以空间复杂度是 O(k)，其中 k 是数组中不同数字的个数。
总结
本题的核心是通过计数和排序来逐步减少数组中的最大值，直到所有元素相等。通过使用 Counter 来统计频次和 sorted 来排序，我们能够高效地计算出最少的操作次数。
希望通过这篇文章，大家对如何解决这类“逐步减少”类型的问题有了更清晰的思路。如果有任何问题，欢迎留言讨论！