LeetCode 题解工作台
使数组为空的最少操作次数
给你一个下标从 0 开始的正整数数组 nums 。 你可以对数组执行以下两种操作 任意次 ： 从数组中选择 两个 值 相等 的元素，并将它们从数组中 删除 。 从数组中选择 三个 值 相等 的元素，并将它们从数组中 删除 。 请你返回使数组为空的 最少 操作次数，如果无法达成，请返回 -1 。 示例…
4
题型
5
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
我们用一个哈希表 统计数组中每个元素出现的次数，然后遍历哈希表，对于每个元素 ，如果 出现的次数为 ，那么我们可以进行 $\lfloor \frac{c+2}{3} \rfloor$ 次操作，将 删除，最后我们返回所有元素的操作次数之和即可。 时间复杂度 ，空间复杂度 。其中 是数组的长度。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个下标从 0 开始的正整数数组 nums 。
你可以对数组执行以下两种操作 任意次 ：
- 从数组中选择 两个 值 相等 的元素，并将它们从数组中 删除 。
- 从数组中选择 三个 值 相等 的元素，并将它们从数组中 删除 。
请你返回使数组为空的 最少 操作次数，如果无法达成，请返回 -1 。
示例 1：
输入：nums = [2,3,3,2,2,4,2,3,4] 输出：4 解释：我们可以执行以下操作使数组为空： - 对下标为 0 和 3 的元素执行第一种操作，得到 nums = [3,3,2,4,2,3,4] 。 - 对下标为 2 和 4 的元素执行第一种操作，得到 nums = [3,3,4,3,4] 。 - 对下标为 0 ，1 和 3 的元素执行第二种操作，得到 nums = [4,4] 。 - 对下标为 0 和 1 的元素执行第一种操作，得到 nums = [] 。 至少需要 4 步操作使数组为空。
示例 2：
输入：nums = [2,1,2,2,3,3] 输出：-1 解释：无法使数组为空。
提示：
2 <= nums.length <= 1051 <= nums[i] <= 106
解题思路
方法一：哈希表 + 贪心
我们用一个哈希表 统计数组中每个元素出现的次数，然后遍历哈希表，对于每个元素 ，如果 出现的次数为 ，那么我们可以进行 次操作，将 删除，最后我们返回所有元素的操作次数之和即可。
时间复杂度 ，空间复杂度 。其中 是数组的长度。
class Solution:
def minOperations(self, nums: List[int]) -> int:
count = Counter(nums)
ans = 0
for c in count.values():
if c == 1:
return -1
ans += (c + 2) // 3
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(N) |
| 空间 | O(N) |
面试官常问的追问
外企场景- question_mark
Candidate demonstrates a solid understanding of greedy algorithms by focusing on frequency maximization.
- question_mark
The candidate should mention hash table lookups and how they help minimize operations.
- question_mark
Watch for candidates who misunderstand the problem's failure case, returning -1 when the operations aren't applicable.
常见陷阱
外企场景- error
Failing to handle cases where the array cannot be emptied, such as when no elements have a frequency greater than 1.
- error
Overcomplicating the solution by not leveraging a hash table to track frequencies.
- error
Using inefficient algorithms that lead to excessive time complexity, especially for large arrays.
进阶变体
外企场景- arrow_right_alt
Consider cases where the array contains only one distinct element.
- arrow_right_alt
Handle the case when all elements are distinct, and no operations can be applied.
- arrow_right_alt
Introduce constraints like different operation types or modifying the frequency constraints.