LeetCode 题解工作台
O(1) 时间插入、删除和获取随机元素 - 允许重复
RandomizedCollection 是一种包含数字集合(可能是重复的)的数据结构。它应该支持插入和删除特定元素，以及删除随机元素。 实现 RandomizedCollection 类: RandomizedCollection() 初始化空的 RandomizedCollection 对象。 …
5
题型
2
代码语言
3
相关题
当前训练重点
困难 · 数组·哈希·扫描
答案摘要
class RandomizedCollection: def __init__(self):
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
RandomizedCollection 是一种包含数字集合(可能是重复的)的数据结构。它应该支持插入和删除特定元素，以及删除随机元素。
实现 RandomizedCollection 类:
RandomizedCollection()初始化空的RandomizedCollection对象。bool insert(int val)将一个val项插入到集合中，即使该项已经存在。如果该项不存在，则返回true，否则返回false。bool remove(int val)如果存在，从集合中移除一个val项。如果该项存在，则返回true，否则返回false。注意，如果val在集合中出现多次，我们只删除其中一个。int getRandom()从当前的多个元素集合中返回一个随机元素。每个元素被返回的概率与集合中包含的相同值的数量 线性相关 。
您必须实现类的函数，使每个函数的 平均 时间复杂度为 O(1) 。
注意：生成测试用例时，只有在 RandomizedCollection 中 至少有一项 时，才会调用 getRandom 。
示例 1:
输入
["RandomizedCollection", "insert", "insert", "insert", "getRandom", "remove", "getRandom"]
[[], [1], [1], [2], [], [1], []]
输出
[null, true, false, true, 2, true, 1]
解释
RandomizedCollection collection = new RandomizedCollection();// 初始化一个空的集合。
collection.insert(1); // 返回 true，因为集合不包含 1。
// 将 1 插入到集合中。
collection.insert(1); // 返回 false，因为集合包含 1。
// 将另一个 1 插入到集合中。集合现在包含 [1,1]。
collection.insert(2); // 返回 true，因为集合不包含 2。
// 将 2 插入到集合中。集合现在包含 [1,1,2]。
collection.getRandom(); // getRandom 应当:
// 有 2/3 的概率返回 1,
// 1/3 的概率返回 2。
collection.remove(1); // 返回 true，因为集合包含 1。
// 从集合中移除 1。集合现在包含 [1,2]。
collection.getRandom(); // getRandom 应该返回 1 或 2，两者的可能性相同。
提示:
-231 <= val <= 231 - 1insert,remove和getRandom最多 总共 被调用2 * 105次- 当调用
getRandom时，数据结构中 至少有一个 元素
解题思路
方法一
class RandomizedCollection:
def __init__(self):
"""
Initialize your data structure here.
"""
self.m = {}
self.l = []
def insert(self, val: int) -> bool:
"""
Inserts a value to the collection. Returns true if the collection did not already contain the specified element.
"""
idx_set = self.m.get(val, set())
idx_set.add(len(self.l))
self.m[val] = idx_set
self.l.append(val)
return len(idx_set) == 1
def remove(self, val: int) -> bool:
"""
Removes a value from the collection. Returns true if the collection contained the specified element.
"""
if val not in self.m:
return False
idx_set = self.m[val]
idx = list(idx_set)[0]
last_idx = len(self.l) - 1
self.l[idx] = self.l[last_idx]
idx_set.remove(idx)
last_idx_set = self.m[self.l[last_idx]]
if last_idx in last_idx_set:
last_idx_set.remove(last_idx)
if idx < last_idx:
last_idx_set.add(idx)
if not idx_set:
self.m.pop(val)
self.l.pop()
return True
def getRandom(self) -> int:
"""
Get a random element from the collection.
"""
return -1 if len(self.l) == 0 else random.choice(self.l)
# Your RandomizedCollection object will be instantiated and called as such:
# obj = RandomizedCollection()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for candidates who demonstrate a good understanding of hash table operations and array manipulation.
- question_mark
Candidates should highlight the O(1) time complexity for all operations and explain how duplicates are efficiently handled.
- question_mark
Expect candidates to discuss the trade-offs of using an array with a hash map for O(1) random access and insertion/removal.
常见陷阱
外企场景- error
Failing to update the hash map correctly when removing elements, which can lead to incorrect results in subsequent operations.
- error
Overlooking the need to maintain the array’s compactness when removing elements, which could lead to slower operations.
- error
Not fully understanding the implications of storing multiple indices for duplicate values in the hash map, leading to inefficient solutions.
进阶变体
外企场景- arrow_right_alt
Handling large data sets efficiently while maintaining O(1) operations.
- arrow_right_alt
Supporting additional operations like 'getRandomWithFrequency' to retrieve random elements based on their frequency of insertion.
- arrow_right_alt
Optimizing space usage for cases with very sparse data where many indices are empty.