 题解和一些延伸)
1. 题干概述
设计一个支持以下操作的数据结构RandomizedSet：
insert(val)：当元素val不存在时，向集合中插入该元素，并返回True；如果已经存在，返回False。remove(val)：当元素val存在时，从集合中删除该元素，并返回True；如果不存在，返回False。getRandom()：随机返回集合中的一个元素，要求每个元素被返回的概率相同。
要求：
insert平均时间复杂度为O(1)。remove平均时间复杂度为O(1)。getRandom平均时间复杂度为O(1)。
这题的关键不只是写代码，而是理解：如何设计一个自定义类，把多个基础数据结构组合起来，满足特定的复杂度要求。
2. Python 代码题解
importrandomclassRandomizedSet:def__init__(self):self.arr=[]# 动态数组：存储集合中的所有元素self.pos={}# 哈希表：val -> val 在 arr 中的下标definsert(self,val:int)->bool:ifvalinself.pos:returnFalseself.arr.append(val)self.pos[val]=len(self.arr)-1returnTruedefremove(self,val:int)->bool:ifvalnotinself.pos:returnFalseidx=self.pos[val]# 要删除元素的位置last=self.arr[-1]# 当前数组最后一个元素self.arr[idx]=last# 用最后一个元素覆盖要删除的位置self.pos[last]=idx# 更新最后一个元素的新下标self.arr.pop()# 删除数组最后一个位置delself.pos[val]# 删除 val 在哈希表中的记录returnTruedefgetRandom(self)->int:returnrandom.choice(self.arr)3. 为什么要用list + dict？
这题要求三个操作都达到平均O(1)：
insert(val): O(1) remove(val): O(1) getRandom(): O(1)单独使用某一种数据结构很难同时满足。
3.1 只用 list 的问题
list支持随机下标访问，所以getRandom很方便：
random.choice(arr)这可以做到O(1)。
但是如果要删除指定值：
arr.remove(val)需要先从头到尾找到val的位置，时间复杂度是O(n)。
所以只用list不满足删除O(1)。
3.2 只用 set / dict 的问题
set或dict可以快速判断元素是否存在：
valins valind平均时间复杂度是O(1)。
插入和删除也可以做到平均O(1)。
但是set/dict不支持像数组那样的稳定下标访问，不能方便地做到：
随机选一个下标，然后 O(1)返回元素所以只用set/dict不适合实现getRandom()。
3.3 正确组合：list + dict
因此需要组合两种结构：
self.arr=[]# index -> valself.pos={}# val -> index它们分别负责：
list arr：负责 O(1) 随机访问，用于 getRandom() dict pos：负责 O(1) 查找元素位置，用于 insert/remove()这就是这题最核心的设计思想。
4. remove 为什么要“尾元素覆盖”？
删除是这题最巧妙的地方。
如果直接删除数组中间元素，例如：
arr=[10,20,30,40]要删除20，如果使用：
arr.pop(1)数组会变成：
[10,30,40]但这个过程中，30和40都需要向前移动，因此是O(n)。
为了做到O(1)，我们不能保持原顺序，而是利用题目没有要求元素顺序这一点。
删除20的过程如下：
初始状态：
arr=[10,20,30,40]pos={10:0,20:1,30:2,40:3}要删除：
val=20先找到它的位置：
idx=pos[20]# 1取最后一个元素：
last=arr[-1]# 40用最后一个元素覆盖待删除位置：
arr[idx]=last数组临时变成：
[10,40,30,40]更新40的位置：
pos[40]=1再删除尾部旧的40：
arr.pop()最后删除20的哈希表记录：
delpos[20]最终状态：
arr=[10,40,30]pos={10:0,40:1,30:2}整个过程没有移动大量元素，因此是O(1)。
5. 代码细节注意点
5.1 为什么先更新pos[last]，再删除pos[val]？
代码为：
idx=self.pos[val]last=self.arr[-1]self.arr[idx]=last self.pos[last]=idx self.arr.pop()delself.pos[val]这个顺序一般是安全且清晰的。
即使删除的是最后一个元素本身，例如：
arr=[10,20,30]remove(30)此时：
idx=2last=30执行：
self.arr[idx]=last self.pos[last]=idx self.arr.pop()delself.pos[val]虽然pos[30]被重新赋值了一次，但随后又被删除，所以结果仍然正确。
5.2 为什么getRandom是 O(1)？
returnrandom.choice(self.arr)random.choice会从列表中随机选择一个下标，并返回该下标对应的元素。
由于列表支持O(1)下标访问，所以getRandom的平均时间复杂度是O(1)。
同时，因为每个元素在arr中只出现一次，而每个下标被选中的概率相同，所以每个元素被返回的概率也相同。
6. 复杂度分析
| 操作 | 时间复杂度 | 原因 |
|---|---|---|
insert(val) | 平均O(1) | dict查重 +list.append |
remove(val) | 平均O(1) | dict定位 + 尾元素覆盖 +pop |
getRandom() | O(1) | list支持随机下标访问 |
| 额外空间 | O(n) | 同时维护arr和pos |
注意：dict的O(1)通常指平均复杂度，极端哈希冲突下理论上可能退化，但刷题中一般按平均O(1)处理。
7. 这题更宽泛的思想
这题不是单纯考 API，而是在考数据结构设计能力。
核心思想是：
为了满足一组操作的时间复杂度要求，可以组合多个基础数据结构，并维护它们之间的一致性。也可以总结为：
用空间换时间。RandomizedSet维护了两份信息：
arr:index->val pos:val->index它们是互相对应的反向索引。
这样做的代价是多用了O(n)空间，但换来了三个操作的平均O(1)时间。
8. 自定义类可以做到什么程度？
自定义类的上限取决于：
你内部组合了什么数据结构； 你额外维护了什么信息； 你愿意为某些操作付出多少空间或维护成本。普通list删除指定值是O(n)，但如果自定义类额外维护：
val->index就可以把“找到这个值的位置”变成O(1)。
所以自定义类可以做到：
1. 对外提供统一接口。 2. 内部组合多个数据结构。 3. 为高频操作维护额外索引。 4. 在每次增删改时维护内部状态一致。但是，不是所有操作都能强行做到O(1)。
例如，如果要求：
删除任意元素，同时保持数组原有顺序那一般无法做到O(1)，因为删除中间元素后，后面的元素必须整体前移。
因此这题能够做到O(1)删除，有一个重要前提：
集合内部元素顺序不重要。如果顺序不重要，就可以用最后一个元素覆盖待删除位置，从而避免移动大量元素。
9. 这个类在实践中有用吗？
有用。
这种结构适用于需要维护动态集合，并且经常随机采样的场景。
例如：
在线用户池中随机抽一个用户； 游戏中随机抽一个可用对象； 推荐系统中从候选池随机采样； 机器学习中的 negative sampling； 随机测试数据生成； 任务池中随机选择一个任务； 缓存系统中随机淘汰某个 key。真实工程中还可能需要考虑：
线程安全； 并发读写； 随机数种子； 内存占用； 是否允许重复元素； 是否需要加权随机采样； 是否需要保持插入顺序。但这题的核心结构list + dict本身是非常实用的。
10. 常见数据结构增删查改复杂度复习
10.1 list：动态数组
Python 的list底层可以理解为动态数组。
特点：
连续内存 + 下标访问| 操作 | 时间复杂度 | 原因 |
|---|---|---|
nums[i] | O(1) | 根据下标直接计算位置 |
nums[i] = x | O(1) | 找到位置后直接覆盖 |
append(x) | 平均O(1) | 动态数组通常预留额外容量 |
pop() | O(1) | 删除最后一个元素 |
insert(i, x) | O(n) | 后面元素需要整体后移 |
pop(i) | O(n) | 后面元素需要整体前移 |
x in nums | O(n) | 需要线性扫描 |
nums.index(x) | O(n) | 需要线性查找 |
sort() | O(n log n) | 排序算法复杂度 |
为什么下标访问是O(1)？
数组元素逻辑上连续存放，可以通过：
元素地址 = 起始地址 + 下标偏移直接定位。
10.2 dict：哈希表
Python 的dict底层是哈希表。
特点：
key -> hash(key) -> 哈希表位置| 操作 | 平均复杂度 | 最坏复杂度 | 原因 |
|---|---|---|---|
d[key] | O(1) | O(n) | 通过哈希定位 |
d[key] = val | O(1) | O(n) | 哈希定位后插入或覆盖 |
del d[key] | O(1) | O(n) | 哈希定位后删除 |
key in d | O(1) | O(n) | 哈希查询 |
遍历dict | O(n) | O(n) | 每个键值都要访问 |
刷题里通常把dict的查询、插入、删除视为平均O(1)。
10.3 set：只有 key 的哈希表
set可以理解为只有 key、没有 value 的dict。
适合处理：
去重； 判断元素是否存在； 集合运算。| 操作 | 平均复杂度 | 原因 |
|---|---|---|
x in s | O(1) | 哈希查询 |
s.add(x) | O(1) | 哈希插入 |
s.remove(x) | O(1) | 哈希删除，不存在会报错 |
s.discard(x) | O(1) | 哈希删除，不存在也不报错 |
遍历set | O(n) | 每个元素都要访问 |
缺点：
不支持按下标访问； 不适合直接 O(1) 随机取元素； 不天然维护排序。10.4 deque：双端队列
collections.deque是双端队列。
适合：
队头和队尾频繁插入删除。| 操作 | 时间复杂度 | 原因 |
|---|---|---|
append(x) | O(1) | 尾部插入 |
appendleft(x) | O(1) | 头部插入 |
pop() | O(1) | 尾部删除 |
popleft() | O(1) | 头部删除 |
中间访问dq[i] | O(n) | 不像数组连续随机访问 |
| 中间插入/删除 | O(n) | 需要定位或移动 |
如果要做队列，不推荐使用：
list.pop(0)因为它是O(n)。
推荐使用：
fromcollectionsimportdeque q=deque()q.append(x)q.popleft()10.5 heapq：堆 / 优先队列
Python 中常用heapq实现小根堆。
适合：
快速获取当前最小值； 维护 Top K； 优先队列； Dijkstra 等算法。| 操作 | 时间复杂度 | 原因 |
|---|---|---|
heap[0] | O(1) | 堆顶就是最小元素 |
heappush(heap, x) | O(log n) | 插入后需要上浮 |
heappop(heap) | O(log n) | 删除堆顶后需要下沉 |
heapify(arr) | O(n) | 批量建堆 |
| 查找任意元素 | O(n) | 堆不是为搜索设计的 |
堆可以看成一棵完全二叉树，高度约为log n，所以插入和删除堆顶是O(log n)。
10.6 链表 Linked List
Python 刷题中常见链表题，但日常使用不如list、dict常见。
链表特点：
节点不连续； 每个节点通过指针连接下一个节点。| 操作 | 时间复杂度 | 原因 |
|---|---|---|
| 已知节点后插入 | O(1) | 改指针即可 |
| 已知前驱节点后删除 | O(1) | 改指针即可 |
| 查找某个值 | O(n) | 需要从头遍历 |
| 按下标访问 | O(n) | 不能通过地址偏移直接定位 |
| 头部插入/删除 | O(1) | 修改 head 指针 |
链表和数组的核心区别：
数组：下标访问快，中间插删慢。 链表：已知位置插删快，查找和下标访问慢。注意：链表删除快的前提是已经拿到了目标节点或前驱节点。若还要先查找，整体仍然是O(n)。
10.7 str：字符串
Python 字符串是不可变对象。
| 操作 | 时间复杂度 | 原因 |
|---|---|---|
s[i] | O(1) | 下标访问 |
s + t | O(len(s) + len(t)) | 生成新字符串 |
s[a:b] | O(k) | 切片会复制长度为 k 的子串 |
char in s | O(n) | 线性扫描 |
''.join(arr) | O(n) | 一次性合并所有字符或字符串片段 |
因为字符串不可变，所以频繁使用：
s+=piece可能产生较大开销。
更推荐：
parts=[]parts.append(piece)result=''.join(parts)11. 总表复习
| 数据结构 | 底层思想 | 优势 | 劣势 |
|---|---|---|---|
list | 动态数组 | 下标访问快，尾部增删快 | 中间插删慢，查值慢 |
dict | 哈希表 | 查询、插入、删除平均O(1) | 不适合按下标随机访问 |
set | 哈希表 | 去重和存在性判断快 | 无下标，无 value |
deque | 双端队列 | 头尾增删快 | 中间访问慢 |
heapq | 二叉堆 | 快速取最小值 | 查找任意元素慢 |
| 链表 | 指针节点 | 已知位置插删快 | 查找和下标访问慢 |
str | 不可变字符序列 | 访问方便，语义安全 | 修改和拼接会复制 |
