NeetCode #127LC-380MediumArrays & Hashing
← Back to All Problems#127 · #380 · Insert Delete GetRandom O(1)(O(1) 时间插入、删除和获取随机元素)
📌 Problem Statement & Constraints
Design a data structure that supports
insert(val), remove(val) and getRandom() in average O(1) time. insert returns whether the value was newly added, remove returns whether the value existed, and getRandom returns a uniformly random existing element. Constraints: -2^31 <= val <= 2^31 - 1; at most 2 * 10^5 calls.💡 Core Algorithmic Approaches
- An array alone gives O(1) random access but O(n) removal; a hash map alone gives O(1) insert/remove but cannot sample uniformly without materialising the keys.
- Combine them: the array stores the values, and the map stores each value's index in the array.
remove(val)swaps the target with the last element, updates the moved element's index, then pops the array -- O(1) overall.getRandompicks a uniform index withrandom.choice, which is O(1).
💻 Benchmark Python3 Implementation
import random
class RandomizedSet:
def __init__(self):
self.arr = [] # the values
self.pos = {} # value -> index in arr
def insert(self, val: int) -> bool:
if val in self.pos:
return False
self.pos[val] = len(self.arr)
self.arr.append(val)
return True
def remove(self, val: int) -> bool:
if val not in self.pos:
return False
i = self.pos[val]
last = self.arr[-1]
self.arr[i] = last # move the last element into the hole
self.pos[last] = i
self.arr.pop()
del self.pos[val] # must come after the reassignment
return True
def getRandom(self) -> int:
return random.choice(self.arr)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(1) average per operation: array append/pop are amortised O(1) and hash operations are O(1) on average.
💾 Space Complexity
O(n) for the array and the index map.
⚠️ Interview Pitfalls & Follow-ups
- Deleting from the map before moving the last element: when the removed value is the last element,
self.pos[last] = iwould recreate the entry you just deleted. Order matters. - Removing from the array with
arr.remove(val): O(n) because of the shift. - Using
setand converting to a list ingetRandom: O(n) per call. - Forgetting to update the moved element's index: the map would point at a stale position, breaking later removals.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🧩 Related Arrays & Hashing Problems
中文速览与面试要点
O(1) 时间插入、删除和获取随机元素
实现 RandomizedSet 类: insert(val) 当元素 val 不存在时,向集合中插入该项,并返回 true;否则返回 false。 remove(val) 当元素 val 存在时,从集合中移除该项,并返回 true;否则返回 false。 getRandom() 随机返回现有集合中的一项(测试用例保证调用此方法时集合中至少存在一个元素)。每个元素应该有 相同的概率 被返回。要求:所有函数平均时间复杂度为 O(1)。约束:-2^31 ≤ val ≤ 2^31 − 1;最多调用 2 × 10^5 次 insert / remove / getRandom。
核心要点
- 数组 + 哈希表(标准解) :数组 arr 支持 O(1) 随机访问(用于 getRandom),哈希表 pos 记录「值 → 在数组中的下标」(用于 O(1) 判存与定位)。
- insert :若值已在 pos 中则返回 False;否则追加到数组末尾并在 pos 中记录下标。
- remove 的关键技巧(本题核心) :把待删元素与数组 末尾元素交换 ,然后弹出末尾。这样避免了下标 O(n) 的搬移。交换后必须同步更新 pos 中末尾元素的新下标。
- getRandom : random.choice(arr) 或 arr[random.randrange(len(arr))] ,每个元素被选中的概率均为 1/n。
常见陷阱
- remove 时直接 arr.remove(val) :list 的 remove 是 O(n) 查找 + O(n) 搬移,违反 O(1) 要求。必须用「与末尾交换」的技巧。
- 交换后忘记更新 pos 中末尾元素的下标 : pos[last] = i 这一行是必须的,漏掉会导致后续按 pos 定位时找到错误位置。
- 先 arr.pop() 再 del self.pos[val] 但 val 恰好是末尾元素 :本解通过「先赋值 pos[last] = i 再 del pos[val] 」的顺序正确处理了这一情形(当 val 就是末尾元素时, pos[last] = i 设置的就是 pos[val] ,随后被 del 删除,结果正确)。
- 用集合实现 getRandom :集合不支持下标访问,无法在 O(1) 内随机取元素(转列表是 O(n))。
参考实现
import random
class RandomizedSet:
def __init__(self):
self.arr = [] # 支持 O(1) 随机访问
self.pos = {} # 值 -> 在 arr 中的下标
def insert(self, val: int) -> bool:
if val in self.pos:
return False
self.pos[val] = len(self.arr)
self.arr.append(val)
return True
def remove(self, val: int) -> bool:
if val not in self.pos:
return False
i = self.pos[val] # 待删位置
last = self.arr[-1] # 末尾元素
self.arr[i] = last # 用末尾元素填补空洞
self.pos[last] = i # 同步更新末尾元素的下标
self.arr.pop() # 弹出末尾
del self.pos[val]
return True
def getRandom(self) -> int:
return random.choice(self.arr)