O(1) 时间插入、删除和获取随机元素
Insert Delete GetRandom O(1)
本机进度仅保存在当前浏览器
题目描述
实现 RandomizedSet 类：insert(val) 不存在时插入并返回 true；remove(val) 存在时删除并返回 true；getRandom() 等概率返回现有元素之一。三个方法平均时间复杂度都要求 O(1)。
示例：依次 insert(1)、remove(2)、insert(2)、getRandom() 从 {1, 2} 等概率返回。
解题思路
- 单用哈希表无法等概率随机取值，单用数组无法 O(1) 删除——两者结合：数组存元素，哈希表存「值 -> 数组下标」。
- 随机取值直接对数组下标抽样，O(1)。
- 删除的技巧是把待删元素与数组末尾交换后 pop：先改哈希表映射，再改数组，保持两者一致。
参考实现
查看参考实现Python · 建议先自行作答
import random
class RandomizedSet:
def __init__(self):
self.items = [] # 值的动态数组
self.pos = {} # 值 -> 数组下标
def insert(self, val):
if val in self.pos:
return False
self.pos[val] = len(self.items)
self.items.append(val)
return True
def remove(self, val):
if val not in self.pos:
return False
# 末尾元素补到被删位置再弹出，保持 O(1)
i = self.pos.pop(val)
last = self.items.pop()
if i < len(self.items):
self.items[i] = last
self.pos[last] = i
return True
def getRandom(self):
return random.choice(self.items)