LeetCode 题解工作台
使数组元素互不相同所需的最少操作次数
给你一个整数数组 nums ，你需要确保数组中的元素 互不相同 。为此，你可以执行以下操作任意次： 从数组的开头移除 3 个元素。如果数组中元素少于 3 个，则移除所有剩余元素。 注意： 空数组也视作为数组元素互不相同。返回使数组元素互不相同所需的 最少操作次数 。 示例 1： 输入： nums =…
2
题型
6
代码语言
3
相关题
当前训练重点
简单 · 数组·哈希·扫描
答案摘要
我们可以倒序遍历数组 ，并使用哈希表 记录已经遍历过的元素。当遍历到元素 时，如果 已经在哈希表 中，那么说明我们需要移除 的所有元素，需要的操作次数为 $\left\lfloor \frac{i}{3} \right\rfloor + 1$。否则，我们将 加入哈希表 中，并继续遍历下一个元素。 遍历结束后，如果没有找到重复的元素，那么数组中的元素已经互不相同，不需要进行任何操作，答…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个整数数组 nums，你需要确保数组中的元素 互不相同 。为此，你可以执行以下操作任意次：
- 从数组的开头移除 3 个元素。如果数组中元素少于 3 个，则移除所有剩余元素。
注意：空数组也视作为数组元素互不相同。返回使数组元素互不相同所需的 最少操作次数 。
示例 1：
输入： nums = [1,2,3,4,2,3,3,5,7]
输出： 2
解释：
- 第一次操作：移除前 3 个元素，数组变为
[4, 2, 3, 3, 5, 7]。 - 第二次操作：再次移除前 3 个元素，数组变为
[3, 5, 7]，此时数组中的元素互不相同。
因此，答案是 2。
示例 2：
输入： nums = [4,5,6,4,4]
输出： 2
解释：
- 第一次操作：移除前 3 个元素，数组变为
[4, 4]。 - 第二次操作：移除所有剩余元素，数组变为空。
因此，答案是 2。
示例 3：
输入： nums = [6,7,8,9]
输出： 0
解释：
数组中的元素已经互不相同，因此不需要进行任何操作，答案是 0。
提示：
1 <= nums.length <= 1001 <= nums[i] <= 100
解题思路
方法一：哈希表 + 倒序遍历
我们可以倒序遍历数组 ，并使用哈希表 记录已经遍历过的元素。当遍历到元素 时，如果 已经在哈希表 中，那么说明我们需要移除 的所有元素，需要的操作次数为 。否则，我们将 加入哈希表 中，并继续遍历下一个元素。
遍历结束后，如果没有找到重复的元素，那么数组中的元素已经互不相同，不需要进行任何操作，答案为 。
时间复杂度 ，空间复杂度 。其中 为数组 的长度。
class Solution:
def minimumOperations(self, nums: List[int]) -> int:
s = set()
for i in range(len(nums) - 1, -1, -1):
if nums[i] in s:
return i // 3 + 1
s.add(nums[i])
return 0
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n) |
| 空间 | O(n) |
面试官常问的追问
外企场景- question_mark
Can the candidate recognize that the problem is best solved with an array scan and hash table approach?
- question_mark
Does the candidate consider efficient ways to handle duplicates using the constraints?
- question_mark
Is the candidate aware of the potential to optimize this solution even further?
常见陷阱
外企场景- error
Not utilizing a hash table to track element frequencies and relying on brute force solutions which are less efficient.
- error
Changing an element to a duplicate number, causing more operations than necessary.
- error
Ignoring the constraints and trying complex solutions when a simple approach suffices due to the small array size.
进阶变体
外企场景- arrow_right_alt
Handling arrays with larger sizes while maintaining efficient operations.
- arrow_right_alt
Considering edge cases like empty arrays or arrays with only one element.
- arrow_right_alt
Exploring other methods of tracking duplicates besides hash tables, like sorting or using counters.