LeetCode 380：Insert Delete GetRandom O(1) 题解和一些延伸

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. 复杂度分析

注意：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底层可以理解为动态数组。

特点：

连续内存 + 下标访问

为什么下标访问是O(1)？

数组元素逻辑上连续存放，可以通过：

元素地址 = 起始地址 + 下标偏移

直接定位。

10.2 dict：哈希表

Python 的dict底层是哈希表。

特点：

key -> hash(key) -> 哈希表位置

刷题里通常把dict的查询、插入、删除视为平均O(1)。

10.3 set：只有 key 的哈希表

set可以理解为只有 key、没有 value 的dict。

适合处理：

去重； 判断元素是否存在； 集合运算。

缺点：

不支持按下标访问； 不适合直接 O(1) 随机取元素； 不天然维护排序。

10.4 deque：双端队列

collections.deque是双端队列。

适合：

队头和队尾频繁插入删除。

如果要做队列，不推荐使用：

list.pop(0)

因为它是O(n)。

推荐使用：

fromcollectionsimportdeque q=deque()q.append(x)q.popleft()

10.5 heapq：堆 / 优先队列

Python 中常用heapq实现小根堆。

适合：

快速获取当前最小值； 维护 Top K； 优先队列； Dijkstra 等算法。

堆可以看成一棵完全二叉树，高度约为log n，所以插入和删除堆顶是O(log n)。

10.6 链表 Linked List

Python 刷题中常见链表题，但日常使用不如list、dict常见。

链表特点：

节点不连续； 每个节点通过指针连接下一个节点。

链表和数组的核心区别：

数组：下标访问快，中间插删慢。 链表：已知位置插删快，查找和下标访问慢。

注意：链表删除快的前提是已经拿到了目标节点或前驱节点。若还要先查找，整体仍然是O(n)。

10.7 str：字符串

Python 字符串是不可变对象。

因为字符串不可变，所以频繁使用：

s+=piece

可能产生较大开销。

更推荐：

parts=[]parts.append(piece)result=''.join(parts)

11. 总表复习