AlgoNote 算法题解：LeetCode 0380 常数时间插入、删除和获取随机元素（数组 + 哈希表设计）

• 教程
• 文档
• 知识库

本篇是 AlgoNote「算法通关手册」中 0380. 常数时间插入、删除和获取随机元素 的深度解读：围绕"哈希表记录下标 + 动态数组末尾交换删除"这一经典设计思路，逐行剖析 Python 实现，并结合仓库内 0381（允许重复）、0382（链表随机节点）、0384（打乱数组）等随机化系列题目进行横向拓展，帮助读者掌握这类"O(1) 数据结构设计"题目的通用解法。

一、题目概述

1.1 题目要求

设计一个数据结构RandomizedSet，支持以下三个操作，且每个操作的平均时间复杂度均为 O(1)：

• insert(val)：当元素val不存在时，向集合中插入该项；若已存在则不做任何操作。
• remove(val)：当元素val存在时，从集合中移除该项。
• getRandom()：随机返回现有集合中的一项，每个元素应有相同的概率被返回。

题目标签为：设计、数组、哈希表、数学、随机化，难度为中等。完整题目描述与约束可见 原题解析文档。

1.2 为什么直接使用朴素结构不行

单独使用任一结构都无法同时满足三个 O(1) 约束：

• 动态数组支持按下标随机访问，但按值删除需要线性扫描；
• 哈希表支持按值 O(1) 判重与删除，但集合内部是无序的，无法做到"等概率随机返回其中一项"。

这正是题目"设计"标签的用意所在——用组合结构扬长避短。

二、核心思路：数组存元素 + 哈希表存下标

原文档给出的解题思路非常凝练，其核心可以总结为一句话：

利用哈希表记录每个元素在数组中的下标，使"按值定位"从 O(n) 降为 O(1)；删除时通过"与末尾元素交换再弹出"避免数组整体搬移。

具体对应到三个操作：

1. 插入操作：将元素直接插入到数组尾部，并在哈希表中记录该元素的下标位置（即len(list)，插入前的数组长度）。
2. 删除操作：先用哈希表找到待删除元素在数组中的位置；将该位置与数组末尾元素互换；更新哈希表中"被换到前面来的末尾元素"的下标值；最后弹出数组末尾元素并删除哈希表中待删除元素的记录。
3. 获取随机元素：使用 Python 标准库random.choice(list)从数组中随机取一个元素，天然等概率。

2.1 关键技巧：交换删除（swap-and-pop）

直接list.pop(idx)虽然能删除指定位置，但会导致该位置之后的所有元素前移，最坏为 O(n)。而"交换末尾 + 弹出末尾"（即 swap-and-pop 技巧）让删除固定发生在数组尾部，配合哈希表同步更新被交换元素的新下标，三个操作便全部收敛为常数时间。

三、Python 完整实现

以下代码即为原文档给出的完整实现（random为 Python 标准库，无需第三方依赖）：

import random class RandomizedSet: def __init__(self): """ Initialize your data structure here. """ self.dict = dict() # 值 -> 下标 self.list = list() # 存储元素的动态数组 def insert(self, val: int) -> bool: """ Inserts a value to the set. Returns true if the set did not already contain the specified element. """ if val in self.dict: return False self.dict[val] = len(self.list) # 记录新元素下标 = 插入前数组长度 self.list.append(val) # 追加到数组尾部 return True def remove(self, val: int) -> bool: """ Removes a value from the set. Returns true if the set contained the specified element. """ if val in self.dict: idx = self.dict[val] # 1. 哈希表定位待删元素下标 last = self.list[-1] # 2. 取出末尾元素 self.list[idx] = last # 3. 末尾元素覆盖待删位置 self.dict[last] = idx # 4. 更新末尾元素的新下标 self.list.pop() # 5. 弹出数组末尾（即被删除的 val） self.dict.pop(val) # 6. 删除哈希表记录 return True return False def getRandom(self) -> int: """ Get a random element from the set. """ return random.choice(self.list)

3.1 逐行拆解：insert

• val in self.dict：O(1) 判重，保证集合语义（元素唯一）。
• self.dict[val] = len(self.list)：此时list尚未追加元素，len恰好是新元素将要落入的下标。
• self.list.append(val)：追加到尾部，数组内元素顺序即下标顺序，保证dict记录与数组实际位置一致。
• 返回True表示插入成功（此前不存在）。

3.2 逐行拆解：remove（最关键的 6 步）

1. idx = self.dict[val]：O(1) 拿到待删元素下标。
2. last = self.list[-1]：O(1) 拿到数组末尾元素。
3. self.list[idx] = last：用末尾元素覆盖待删位置，等价于"交换"。
4. self.dict[last] = idx：末尾元素搬家了，同步更新它的下标记录——这一步极易遗漏，是正确性的关键。
5. self.list.pop()：弹出末尾，数组长度减一，被删元素随之消失。
6. self.dict.pop(val)：清理哈希表中待删元素的记录。

一个需要留意的隐藏细节：当待删除元素恰好就是末尾元素时，第 3、4 步执行的是"自己覆盖自己"，dict[last] = idx与删除前保持一致，逻辑依然正确，无需特判。

3.3 getRandom 的等概率性

random.choice(self.list)基于random.randint均匀采样，数组中每个元素被选中的概率均为1 / len(self.list)，严格满足题目"每个元素相同概率返回"的要求。同时因为数组是连续、紧凑存储的（删除后不存在空洞），随机下标永远不会指向无效位置。

四、复杂度与正确性分析

正确性依据：dict中每个值对应的下标始终与list中的真实位置保持同步——插入时同步登记，删除交换时同步改写，因此任何时候dict[val] == list.index(val)都成立（严格说list中每个元素唯一，二者一一对应），三个操作的语义不会因交换删除而破坏。

五、边界情况与易错点归纳

• 重复插入：insert必须返回False且不改变任何状态，代码通过先判val in self.dict保证幂等。
• 删除不存在的元素：remove返回False，且不能访问self.list[-1]（空数组时会抛IndexError），代码通过判存在性先行短路。
• 空集合调用 getRandom：题目保证调用时集合非空；若自行在空数组上调用random.choice会抛IndexError，实际使用中需自行保证非空。
• 交换后忘记更新dict[last]：这是该解法最常见的 bug，会导致后续删除last时定位到旧下标，破坏数组一致性。
• 删除末尾元素自身：无需特判，交换覆盖操作对"自覆盖"天然正确。

六、横向拓展：从 0380 到随机化设计系列

该题属于典型的"数据结构设计 + 随机化"题型，AlgoNote 仓库在 0300-0399 章节索引 中围绕同一主题收录了多道变体题，对比阅读可以加深理解。

6.1 升级版：0381 允许重复的随机集合

0381. O(1) 时间插入、删除和获取随机元素 - 允许重复 是本题的困难版：集合中允许存在重复值，getRandom的返回概率与相同值的数量线性相关（如集合[1,1,2]中返回 1 的概率为 2/3）。

其解法在本题基础上将哈希表的值从"单个下标"升级为"下标集合"：

from collections import defaultdict class RandomizedCollection: def __init__(self): self.nums = [] # 存储所有元素的数组 self.indices = defaultdict(set) # 值 -> 该值所有下标的集合 def insert(self, val: int) -> bool: self.nums.append(val) self.indices[val].add(len(self.nums) - 1) return len(self.indices[val]) == 1 # 是否首次出现 def remove(self, val: int) -> bool: if not self.indices[val]: return False index = self.indices[val].pop() # 取该值任意一个下标 last_val = self.nums[-1] if index != len(self.nums) - 1: self.nums[index] = last_val self.indices[last_val].discard(len(self.nums) - 1) self.indices[last_val].add(index) self.nums.pop() if not self.indices[val]: del self.indices[val] return True def getRandom(self) -> int: return random.choice(self.nums)

与 0380 的差异点值得注意：

• 插入不再判重，而是通过"该值下标集合是否恰好为 1 个"判断是否首次出现；
• 删除时用set.pop()取该值的任意一个下标，删除后若该值下标集合为空才从字典中移除；
• 交换末尾元素时使用discard移除旧下标（即使该下标已被pop拿走也不会报错），再add新下标；
• 空间复杂度仍为 O(n)，但下标集合整体需要额外维护。

完整推导、示例与复杂度分析见 0381 题解文档。

6.2 姊妹题：0382 链表随机节点

0382. 链表随机节点 同样是"等概率随机返回一项"，但数据结构是长度未知的链表，无法按下标 O(1) 随机访问。解法切换为水塘抽样（Reservoir Sampling）：一次遍历中，对第 i 个节点以1/i概率选中（random.randint(0, i-1) == 0），数学上可证明每个节点最终被选中的概率均为1/n，且空间复杂度为 O(1)。该题是"未知长度随机采样"场景的经典代表，与 0380 形成鲜明对比：能按下标随机就用数组+哈希表，不能按下标随机就用水塘抽样。

6.3 姊妹题：0384 打乱数组

0384. 打乱数组 要求数组所有排列等概率出现，解法为洗牌算法（Fisher-Yates）：从第 0 位到第 n-1 位，每轮从剩余元素中随机选一个与本位交换，使每个位置上的每个元素被选中的概率均为1/n。它与 0380 同属"随机化 + 数组"主题，但目标从"随机读取"变为"随机排列"，可对照阅读。

6.4 相关题目：0398 随机数索引

0398. 随机数索引 同样结合了哈希表与随机化（处理重复元素等概率返回），可作为进阶练习。完整题目列表可查阅 题库分类目录 与 题解列表。

七、底层原理支撑：哈希表基础

本题解法的理论基础建立在哈希表之上。仓库的 03_06 哈希表 章节系统讲解了：

• 哈希表本质：通过哈希函数将键key映射到数组中的存储位置，插入与查找均靠同一哈希函数定位区块；
• 哈希函数设计：直接定址法、除留余数法（Hash(key) = key % p）、平方取中法、基数转换法等；
• 哈希冲突解决：开放地址法（线性/二次/伪随机探查）与链地址法两大策略。

在 0380 的实现中，Python 内置dict已经封装了哈希计算与冲突处理，我们实际利用的是其O(1) 平均查找/插入语义来建立"值 → 下标"的映射关系——这正是哈希表在"设计类"题目中最典型的应用方式。

八、总结

0380 是一道"设计 + 随机化"的高频面试题，核心收获有三点：

1. 组合结构思想：单个数据结构难以同时满足多个 O(1) 约束时，用"数组 + 哈希表"分工协作——数组保证随机访问与紧凑存储，哈希表保证按值定位。
2. 交换删除技巧：删除操作固定发生在数组末尾，避免元素搬移，这是将删除降到 O(1) 的通用手法，在 0381、部分链表与区间操作题目中同样适用。
3. 随机化三件套：按下标随机（0380 的random.choice）、未知长度随机（0382 的水塘抽样）、随机排列（0384 的洗牌算法）构成了随机化题目的完整知识图谱。

建议读者结合 0380 原题文档 与 0381 升级版 逐行手写实现，重点体会"交换后同步更新哈希表下标"这一细节，再通过 0382、0384 巩固随机化算法的概率推导。

• 教程
• 文档
• 知识库