教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本篇是 AlgoNote「算法通关手册」中 0380. 常数时间插入、删除和获取随机元素 的深度解读围绕哈希表记录下标 动态数组末尾交换删除这一经典设计思路逐行剖析 Python 实现并结合仓库内 0381允许重复、0382链表随机节点、0384打乱数组等随机化系列题目进行横向拓展帮助读者掌握这类O(1) 数据结构设计题目的通用解法。一、题目概述1.1 题目要求设计一个数据结构RandomizedSet支持以下三个操作且每个操作的平均时间复杂度均为 O(1)insert(val)当元素val不存在时向集合中插入该项若已存在则不做任何操作。remove(val)当元素val存在时从集合中移除该项。getRandom()随机返回现有集合中的一项每个元素应有相同的概率被返回。题目标签为设计、数组、哈希表、数学、随机化难度为中等。完整题目描述与约束可见 原题解析文档。1.2 为什么直接使用朴素结构不行数据结构insertremovegetRandom动态数组仅支持末尾操作O(1)O(n) 查找O(1) 按下标随机哈希表set/dictO(1)O(1)无法按下标随机访问单独使用任一结构都无法同时满足三个 O(1) 约束动态数组支持按下标随机访问但按值删除需要线性扫描哈希表支持按值 O(1) 判重与删除但集合内部是无序的无法做到等概率随机返回其中一项。这正是题目设计标签的用意所在——用组合结构扬长避短。二、核心思路数组存元素 哈希表存下标原文档给出的解题思路非常凝练其核心可以总结为一句话利用哈希表记录每个元素在数组中的下标使按值定位从 O(n) 降为 O(1)删除时通过与末尾元素交换再弹出避免数组整体搬移。具体对应到三个操作插入操作将元素直接插入到数组尾部并在哈希表中记录该元素的下标位置即len(list)插入前的数组长度。删除操作先用哈希表找到待删除元素在数组中的位置将该位置与数组末尾元素互换更新哈希表中被换到前面来的末尾元素的下标值最后弹出数组末尾元素并删除哈希表中待删除元素的记录。获取随机元素使用 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 逐行拆解insertval in self.dictO(1) 判重保证集合语义元素唯一。self.dict[val] len(self.list)此时list尚未追加元素len恰好是新元素将要落入的下标。self.list.append(val)追加到尾部数组内元素顺序即下标顺序保证dict记录与数组实际位置一致。返回True表示插入成功此前不存在。3.2 逐行拆解remove最关键的 6 步idx self.dict[val]O(1) 拿到待删元素下标。last self.list[-1]O(1) 拿到数组末尾元素。self.list[idx] last用末尾元素覆盖待删位置等价于交换。self.dict[last] idx末尾元素搬家了同步更新它的下标记录——这一步极易遗漏是正确性的关键。self.list.pop()弹出末尾数组长度减一被删元素随之消失。self.dict.pop(val)清理哈希表中待删元素的记录。一个需要留意的隐藏细节当待删除元素恰好就是末尾元素时第 3、4 步执行的是自己覆盖自己dict[last] idx与删除前保持一致逻辑依然正确无需特判。3.3 getRandom 的等概率性random.choice(self.list)基于random.randint均匀采样数组中每个元素被选中的概率均为1 / len(self.list)严格满足题目每个元素相同概率返回的要求。同时因为数组是连续、紧凑存储的删除后不存在空洞随机下标永远不会指向无效位置。四、复杂度与正确性分析操作时间复杂度说明insert(val)O(1)哈希表判重/赋值 数组末尾追加remove(val)O(1)哈希表定位 交换覆盖 末尾弹出getRandom()O(1)random.choice均匀随机空间复杂度O(n)哈希表与数组各存一份元素引用n 为集合大小正确性依据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 是一道设计 随机化的高频面试题核心收获有三点组合结构思想单个数据结构难以同时满足多个 O(1) 约束时用数组 哈希表分工协作——数组保证随机访问与紧凑存储哈希表保证按值定位。交换删除技巧删除操作固定发生在数组末尾避免元素搬移这是将删除降到 O(1) 的通用手法在 0381、部分链表与区间操作题目中同样适用。随机化三件套按下标随机0380 的random.choice、未知长度随机0382 的水塘抽样、随机排列0384 的洗牌算法构成了随机化题目的完整知识图谱。建议读者结合 0380 原题文档 与 0381 升级版 逐行手写实现重点体会交换后同步更新哈希表下标这一细节再通过 0382、0384 巩固随机化算法的概率推导。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐LeetCode 380. 常数时间插入、删除和获取随机元素数组 哈希表设计题全解LeetCode 380. 常数时间插入、删除和获取随机元素数组 哈希表设计题全解 本篇技术指南围绕 LeetCode 380「常数时间插入、删除和获取随文档教程知识库Bruce一台ESP32扛起全套渗透测试Bruce一台ESP32扛起全套渗透测试 为什么是它 Bruce 是一款开源的 ESP32 渗透测试固件把 WiFi 攻击、Sub GHz 射频、RFID/教程文档知识库macOS音频路由终极指南BlackHole零延迟虚拟音频驱动完全教程macOS音频路由终极指南BlackHole零延迟虚拟音频驱动完全教程 BlackHole是一款专为macOS设计的现代虚拟音频环回驱动程序允许应用程序之间驱动开发音频处理上一篇终极指南Semantic-UI-React手风琴组件完全使用教程 下一篇Laravel-WeChat 事件系统深度解析掌握5大核心事件处理技巧创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考