LeetCode 题解工作台
使数组元素相等的减少操作次数
给你一个整数数组 nums ，你的目标是令 nums 中的所有元素相等。完成一次减少操作需要遵照下面的几个步骤： 找出 nums 中的 最大 值。记这个值为 largest 并取其下标 i （ 下标从 0 开始计数 ）。如果有多个元素都是最大值，则取最小的 i 。 找出 nums 中的 下一个最大 …
2
题型
7
代码语言
3
相关题
当前训练重点
中等 · 数组·排序
答案摘要
我们首先对数组 进行排序，然后从数组的第二个元素开始遍历，如果当前元素和前一个元素不相等，那么我们就将 加一，表示我们需要将当前元素减小到最小值的操作次数。然后我们将 加上 ，继续遍历下一个元素。 时间复杂度 $O(n \times \log n)$，空间复杂度 $O(\log n)$。其中 是数组 的长度。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·排序 题型思路
题目描述
给你一个整数数组 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 * 1041 <= nums[i] <= 5 * 104
解题思路
方法一：排序
我们首先对数组 进行排序，然后从数组的第二个元素开始遍历，如果当前元素和前一个元素不相等，那么我们就将 加一，表示我们需要将当前元素减小到最小值的操作次数。然后我们将 加上 ，继续遍历下一个元素。
时间复杂度 ，空间复杂度 。其中 是数组 的长度。
class Solution:
def reductionOperations(self, nums: List[int]) -> int:
nums.sort()
ans = cnt = 0
for a, b in pairwise(nums):
if a != b:
cnt += 1
ans += cnt
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n \cdot \log{}n) |
| 空间 | O(\log n) |
面试官常问的追问
外企场景- question_mark
Candidate efficiently utilizes sorting to reduce time complexity.
- question_mark
Candidate demonstrates a clear understanding of reducing elements and tracking operations.
- question_mark
Candidate ensures the solution is optimal by focusing on minimizing the number of operations.
常见陷阱
外企场景- error
Not sorting the array before attempting to reduce elements.
- error
Forgetting to track the number of operations correctly, leading to inefficient solutions.
- error
Overcomplicating the problem by using unnecessary data structures or operations.
进阶变体
外企场景- arrow_right_alt
What if the array contains only one element?
- arrow_right_alt
How does the solution behave with arrays containing repeated elements?
- arrow_right_alt
How would the solution scale if the array had significantly more elements?