 题解和一些延伸)
1. 题干概述设计一个支持以下操作的数据结构RandomizedSetinsert(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:returnFalseidxself.pos[val]# 要删除元素的位置lastself.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}要删除val20先找到它的位置idxpos[20]# 1取最后一个元素lastarr[-1]# 40用最后一个元素覆盖待删除位置arr[idx]last数组临时变成[10,40,30,40]更新40的位置pos[40]1再删除尾部旧的40arr.pop()最后删除20的哈希表记录delpos[20]最终状态arr[10,40,30]pos{10:0,40:1,30:2}整个过程没有移动大量元素因此是O(1)。5. 代码细节注意点5.1 为什么先更新pos[last]再删除pos[val]代码为idxself.pos[val]lastself.arr[-1]self.arr[idx]last self.pos[last]idx self.arr.pop()delself.pos[val]这个顺序一般是安全且清晰的。即使删除的是最后一个元素本身例如arr[10,20,30]remove(30)此时idx2last30执行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.appendremove(val)平均O(1)dict定位 尾元素覆盖 popgetRandom()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] xO(1)找到位置后直接覆盖append(x)平均O(1)动态数组通常预留额外容量pop()O(1)删除最后一个元素insert(i, x)O(n)后面元素需要整体后移pop(i)O(n)后面元素需要整体前移x in numsO(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] valO(1)O(n)哈希定位后插入或覆盖del d[key]O(1)O(n)哈希定位后删除key in dO(1)O(n)哈希查询遍历dictO(n)O(n)每个键值都要访问刷题里通常把dict的查询、插入、删除视为平均O(1)。10.3 set只有 key 的哈希表set可以理解为只有 key、没有 value 的dict。适合处理去重 判断元素是否存在 集合运算。操作平均复杂度原因x in sO(1)哈希查询s.add(x)O(1)哈希插入s.remove(x)O(1)哈希删除不存在会报错s.discard(x)O(1)哈希删除不存在也不报错遍历setO(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 qdeque()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 ListPython 刷题中常见链表题但日常使用不如list、dict常见。链表特点节点不连续 每个节点通过指针连接下一个节点。操作时间复杂度原因已知节点后插入O(1)改指针即可已知前驱节点后删除O(1)改指针即可查找某个值O(n)需要从头遍历按下标访问O(n)不能通过地址偏移直接定位头部插入/删除O(1)修改 head 指针链表和数组的核心区别数组下标访问快中间插删慢。 链表已知位置插删快查找和下标访问慢。注意链表删除快的前提是已经拿到了目标节点或前驱节点。若还要先查找整体仍然是O(n)。10.7 str字符串Python 字符串是不可变对象。操作时间复杂度原因s[i]O(1)下标访问s tO(len(s) len(t))生成新字符串s[a:b]O(k)切片会复制长度为 k 的子串char in sO(n)线性扫描.join(arr)O(n)一次性合并所有字符或字符串片段因为字符串不可变所以频繁使用spiece可能产生较大开销。更推荐parts[]parts.append(piece)result.join(parts)11. 总表复习数据结构底层思想优势劣势list动态数组下标访问快尾部增删快中间插删慢查值慢dict哈希表查询、插入、删除平均O(1)不适合按下标随机访问set哈希表去重和存在性判断快无下标无 valuedeque双端队列头尾增删快中间访问慢heapq二叉堆快速取最小值查找任意元素慢链表指针节点已知位置插删快查找和下标访问慢str不可变字符序列访问方便语义安全修改和拼接会复制
LeetCode 380：Insert Delete GetRandom O(1) 题解和一些延伸
发布时间：2026/6/10 18:19:25
1. 题干概述设计一个支持以下操作的数据结构RandomizedSetinsert(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:returnFalseidxself.pos[val]# 要删除元素的位置lastself.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}要删除val20先找到它的位置idxpos[20]# 1取最后一个元素lastarr[-1]# 40用最后一个元素覆盖待删除位置arr[idx]last数组临时变成[10,40,30,40]更新40的位置pos[40]1再删除尾部旧的40arr.pop()最后删除20的哈希表记录delpos[20]最终状态arr[10,40,30]pos{10:0,40:1,30:2}整个过程没有移动大量元素因此是O(1)。5. 代码细节注意点5.1 为什么先更新pos[last]再删除pos[val]代码为idxself.pos[val]lastself.arr[-1]self.arr[idx]last self.pos[last]idx self.arr.pop()delself.pos[val]这个顺序一般是安全且清晰的。即使删除的是最后一个元素本身例如arr[10,20,30]remove(30)此时idx2last30执行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.appendremove(val)平均O(1)dict定位 尾元素覆盖 popgetRandom()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] xO(1)找到位置后直接覆盖append(x)平均O(1)动态数组通常预留额外容量pop()O(1)删除最后一个元素insert(i, x)O(n)后面元素需要整体后移pop(i)O(n)后面元素需要整体前移x in numsO(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] valO(1)O(n)哈希定位后插入或覆盖del d[key]O(1)O(n)哈希定位后删除key in dO(1)O(n)哈希查询遍历dictO(n)O(n)每个键值都要访问刷题里通常把dict的查询、插入、删除视为平均O(1)。10.3 set只有 key 的哈希表set可以理解为只有 key、没有 value 的dict。适合处理去重 判断元素是否存在 集合运算。操作平均复杂度原因x in sO(1)哈希查询s.add(x)O(1)哈希插入s.remove(x)O(1)哈希删除不存在会报错s.discard(x)O(1)哈希删除不存在也不报错遍历setO(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 qdeque()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 ListPython 刷题中常见链表题但日常使用不如list、dict常见。链表特点节点不连续 每个节点通过指针连接下一个节点。操作时间复杂度原因已知节点后插入O(1)改指针即可已知前驱节点后删除O(1)改指针即可查找某个值O(n)需要从头遍历按下标访问O(n)不能通过地址偏移直接定位头部插入/删除O(1)修改 head 指针链表和数组的核心区别数组下标访问快中间插删慢。 链表已知位置插删快查找和下标访问慢。注意链表删除快的前提是已经拿到了目标节点或前驱节点。若还要先查找整体仍然是O(n)。10.7 str字符串Python 字符串是不可变对象。操作时间复杂度原因s[i]O(1)下标访问s tO(len(s) len(t))生成新字符串s[a:b]O(k)切片会复制长度为 k 的子串char in sO(n)线性扫描.join(arr)O(n)一次性合并所有字符或字符串片段因为字符串不可变所以频繁使用spiece可能产生较大开销。更推荐parts[]parts.append(piece)result.join(parts)11. 总表复习数据结构底层思想优势劣势list动态数组下标访问快尾部增删快中间插删慢查值慢dict哈希表查询、插入、删除平均O(1)不适合按下标随机访问set哈希表去重和存在性判断快无下标无 valuedeque双端队列头尾增删快中间访问慢heapq二叉堆快速取最小值查找任意元素慢链表指针节点已知位置插删快查找和下标访问慢str不可变字符序列访问方便语义安全修改和拼接会复制
