随机访问：LeetCode 380核心设计解析)
刷 LeetCode 380 这道题我前后摸了三遍每一遍感受都不一样。第一次以为题目考的是哈希表写完发现 getRandom 根本没法定点返回第二次改成 ArrayList 加 HashMap以为万事大吉结果 remove 的边界条件把我折腾得不轻第三次才算真正想明白这道题的核心不是某个单独的数据结构而是组合思维——用数组提供随机访问能力用哈希表记录元素到下标的映射再配合一个交换尾部元素再弹出的小技巧把删除的代价从 O(n) 摊平成 O(1)。如果你正在准备算法面试或者想在系统设计里多一点索引思维这道题非常值得好好啃。1. 先看需求三个 O(1) 同时满足为什么难1.1 拆开看每个操作其实都简单题目要设计一个 RandomizedSet支持 insert、remove、getRandom 三个操作且平均时间复杂度均为 O(1)。单独看每个操作确实不算难。insert 在数组尾部追加元素是 O(1)HashSet 的去重判断也是 O(1)remove 在哈希表里删除一个 key 是平均 O(1)getRandom 更是简单数组按下标访问天然就是 O(1)。难就难在同时满足。你没法只用数组完成去重插入和快速删除因为数组要找到某个值所在的位置需要遍历。你也没法只用哈希表完成随机访问因为哈希表一次迭代只能拿到一个不确定顺序的元素就算用迭代器取一个随机位置迭代成本也会随元素量增长。把这三个操作放到同一个数据结构里就需要让它们共享一套状态且互相不拖后腿。这正是这道题最有意思的地方。1.2 常见“错误方案”是如何死掉的很多人的第一反应是 HashSet。想一下能不能用插入去重、删除都能 O(1)但 getRandom 就懵了。HashSet 内部是数组加链表/红黑树的结构迭代器的遍历顺序不保证均匀更不提供随机下标的能力。即使强行通过迭代器取一个 count 再跳过去那也是 O(n)。第二反应是 TreeMap 或 TreeSet。TreeMap 能 O(log n) 插入删除但 getRandom 呢要做到等概率随机返回你需要知道集合的大小 n然后随机生成一个 [0, n) 的排名再通过找第 k 小的逻辑拿到元素这一步是 O(log n) 的不满足 O(1)。还有 LinkedList。链表删除给定值需要先找到节点是 O(n)即使在节点上额外维护索引随机访问依然得从头或者从尾部走做不到随机下标直达。你发现没有这些常用容器各自都有短板。要么丢随机访问要么丢快速查找。能把三者同时撑起来的只有数组 哈希表这个组合。1.3 突破口在于功能拆解这道题的突破口在于把按值定位和按下标定位两个需求拆开。数组提供按下标访问这是 getRandom 想要的。哈希表提供按值查找这是 insert、remove 想要的。哈希表里保存的不只是这个值是否存在而是这个值在数组中的下标。有了这个下标remove 时就能直接知道该删数组里的哪个位置不需要遍历。所以方案模型很清晰一个数组存元素一个哈希表存每个元素在数组中的下标。两个结构通过下标关联起来。不过这里还有一个隐藏的重难点数组删除中间元素时后续元素全部前移这是 O(n)。既然哈希表能定位到下标怎么让删除只动常数级的数据这就引出下一节的核心技巧。2. 核心方案数组存储 哈希表索引2.1 分工合作数组管随机哈希表管定位先用一句话概括整体设计动态数组比如 Java 的 ArrayList负责存储元素值保证 getRandom 可以随机下标访问。哈希表 MapInteger, Integer 负责记录每个值在数组中的下标保证 insert 去重和 remove 定位都是 O(1)。这两个结构之间的桥梁就是下标。insert 时把新元素追加到数组尾部同时记录map.put(val, list.size() - 1)。remove 时先从 map 拿到元素在数组中的下标再做删除。这个结构最大的好处在于数组和哈希表各自只承担一部分职责互不冗余。没有这套分工你很难同时满足按值查和按下标查两个需求。2.2 insert 的完整流程insert 要保证如果元素已存在则插入失败反之插入成功。流程如下查 map如果该值已存在直接返回 false。将值追加到数组尾部。在 map 中记录值 - 数组下标这里的下标就是追加前的数组长度。返回 true。这看起来平淡无奇但有一个细节值得注意追加到数组尾部这个动作保证了每个元素在数组里都占据一个连续位置没有任何空洞。这种紧凑性是 getRandom 能等概率随机返回的基础。如果数组中存在空洞比如删除中间元素后不清除list.size()就不能代表实际元素数量getRandom 就可能在空洞位置取到无效值。所以后续的删除策略也必须维护数组的紧凑性。2.3 remove 的 swap-and-pop 关键逻辑这是整道题的精髓。从数组中删除下标为 index 的元素常规做法是把后面所有元素前移复杂度 O(n)。要变成 O(1)只能换一种思路。既然数组尾部删除是 O(1)那能不能把删除中间元素转换成删除尾部元素答案是可以的而且只有两步将数组最后一个元素 last 搬到被删除元素的位置即list.set(index, last)。删除数组最后一个位置即list.remove(list.size() - 1)。但这样一做last 这个元素在数组里的下标变了。原来它在最后一个位置现在搬到了 index 位置所以必须同步更新 map 里 last 对应的下标map.put(last, index);最后再从 map 里删除目标值 val 的键map.remove(val);整个remove操作围绕用尾部元素补位展开所以叫 swap-and-pop。这里有个隐藏命题如果被删除的元素恰好就是最后一个元素呢此时 index 等于 lastIndex补位相当于自己替换自己map 中 last 的下标并没有变化。逻辑上也能走通但可以加一个判断跳过无意义的赋值让代码更干净。举一个具体例子。数组为[10, 20, 30]map 为{10:0, 20:1, 30:2}。要删除 20index 1last 30。list.set(1, 30)数组变为[10, 30, 30]。map.put(30, 1)map 变为{10:0, 20:1, 30:1}。list.remove(2)数组变为[10, 30]。map.remove(20)map 变为{10:0, 30:1}。注意第 3 步非常重要如果不更新 last 的新下标后续 getRandom 虽然暂时没事但下一次 remove 就会索引错乱数组里的值找错了位置整个结构就崩了。这就是更新 map 的时机和顺序最容易踩的坑。2.4 getRandom 的均匀性getRandom 要求等概率返回现有集合中的一个元素。数组是紧凑的、无空洞的所以list.size()就是当前元素个数。用随机函数生成一个[0, list.size())的下标然后返回list.get(index)即可。只要数组里每个位置都存放着一个有效元素每个元素被抽中的概率就完全相等。反过来如果删除时留下了空洞或者空位随机访问就可能抽到无效数据结果就不对了。实现上需要注意随机数生成器的使用细节Java 的Random.nextInt(n)左闭右开n 必须大于 0Python 的random.choice(nums)会自己处理索引Go 的rand.Intn(n)同理。不要每次都 new 一个随机数生成器尽量复用同一个实例。3. 代码实现与踩坑Java/Go/Python3.1 Java 完整实现import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; import java.util.Random; class RandomizedSet { private final ListInteger list; private final MapInteger, Integer map; private final Random random; public RandomizedSet() { list new ArrayList(); map new HashMap(); random new Random(); } public boolean insert(int val) { if (map.containsKey(val)) { return false; } map.put(val, list.size()); list.add(val); return true; } public boolean remove(int val) { if (!map.containsKey(val)) { return false; } int index map.get(val); int lastIndex list.size() - 1; int last list.get(lastIndex); if (index ! lastIndex) { list.set(index, last); map.put(last, index); } list.remove(lastIndex); map.remove(val); return true; } public int getRandom() { return list.get(random.nextInt(list.size())); } }Java 版本里我特意在 remove 中加了index ! lastIndex的判断。这个判断不是可有可无的优化它能把删除最后一个元素的场景从 swap-and-pop 的正常分支里剥离出来避免对 map 做无意义的put覆盖也让逻辑更直白。另一个 Java 细节是泛型问题。如果题目改成泛型容器map 的 key 是对象containsKey和get走的是equals判断。如果是整数类型在缓存范围内没有问题一旦涉及自定义对象需要保证equals和hashCode正确实现。不要用去比较。3.2 Go 实现与习惯写法import ( math/rand time ) type RandomizedSet struct { m map[int]int arr []int rnd *rand.Rand } func Constructor() RandomizedSet { return RandomizedSet{ m: make(map[int]int), arr: make([]int, 0), rnd: rand.New(rand.NewSource(time.Now().UnixNano())), } } func (s *RandomizedSet) Insert(val int) bool { if _, ok : s.m[val]; ok { return false } s.arr append(s.arr, val) s.m[val] len(s.arr) - 1 return true } func (s *RandomizedSet) Remove(val int) bool { idx, ok : s.m[val] if !ok { return false } lastIdx : len(s.arr) - 1 lastVal : s.arr[lastIdx] s.arr[idx] lastVal s.m[lastVal] idx s.arr s.arr[:lastIdx] delete(s.m, val) return true } func (s *RandomizedSet) GetRandom() int { return s.arr[s.rnd.Intn(len(s.arr))] }Go 版本有几个值得注意的地方rand.New(rand.NewSource(...))创建的是局部随机源并发场景下还需要考虑安全不过 LeetCode 单线程执行没这个压力。remove 里没有像 Java 那样加idx ! lastIdx判断是因为 Go 的切片赋值s.arr[idx] lastVal在 idx 和 lastIdx 相同时完全无副作用s.m[lastVal] idx也只是覆盖成相同的值。代码更短逻辑等价。delete(s.m, val)放在最后和 Java 的map.remove(val)位置相同都必须保证在更新 lastVal 的下标之后执行。如果顺序倒过来就会出现我在后面第 3.4 节说的那种 bug。import random class RandomizedSet: def __init__(self): self.nums [] self.pos {} def insert(self, val: int) - bool: if val in self.pos: return False self.pos[val] len(self.nums) self.nums.append(val) return True def remove(self, val: int) - bool: if val not in self.pos: return False i self.pos[val] last_val self.nums[-1] self.nums[i] last_val self.pos[last_val] i self.nums.pop() del self.pos[val] return True def getRandom(self) - int: return random.choice(self.nums)Python 版本最简洁。注意 remove 的顺序先改数组再改 pos最后del self.pos[val]。这个顺序不能乱。很多人喜欢把两三行写成元组赋值self.nums[i], self.pos[last_val] last_val, i语法上可行但可读性差而且一旦后续逻辑调整很容易摸不清赋值顺序。我建议拆成两行写清楚明白。代码是给人看的不只是给机器跑的。3.4 最容易翻车的三个 Bug第一个 Bugremove 时先删除 map 里的键再做 swap-and-pop。 如果删除的值恰好是数组最后一个元素并且最后一个元素就是被删除元素本身那么 last_val 和 val 是同一个值。你先把del self.pos[val]执行了再做self.pos[last_val] i确实可以把这个键加回来但加的索引是补位之后的正确索引吗要看具体情况。假设nums [1, 2]pos {1:0, 2:1}要删除 2。 如果先执行del pos[2]得到pos {1:0}然后last_val 1nums[1] 1数组变成[1, 1]pos[1] 1nums.pop()后数组是[1]但pos {1:1}。 这里的 1 实际在数组下标 0 的位置pos 却记录成 1。再往后 insert 或 remove 就会把索引彻底搞乱。所以规则是先处理数组并补位更新最后再删除原键。这个顺序在任何语言里都要坚持。第二个 BuggetRandom 在集合为空时调用。 虽然题目保证数据非空时才调用但实际编码如果加一层防御逻辑会更稳。返回一个非法值或者抛异常都行看面试官要求。千万别在nextInt(0)上栽跟头参数必须是正数。第三个 Bug重复插入把 map 里的下标覆盖了。 insert 已经先查了containsKey所以不会出现覆盖。但如果把 insert 实现成先 add 后 put那就可能在重复插入时把旧下标覆盖成新下标而数组里已经有两个重复元素之后 remove 只能删到其中一个剩下一个永远删不掉。题目允许的集合是无重复元素的集合所以必须严格遵守先判存在再插入。4. 复杂度与面试追问4.1 “平均 O(1)”的摊还分析官方说法是平均时间复杂度 O(1)这里的平均来自两层第一层是哈希表本身。哈希表在理想情况下查找和插入是 O(1)但遇到大量哈希冲突时最坏会退化到 O(n)。工程实现通常用链表法或红黑树优化冲突比如 Java 8 的 HashMap 在链表长度超过阈值时会转成红黑树最坏复杂度降到 O(log n)。第二层是动态数组扩容。ArrayList 每次容量不够时会申请一块更大的空间并复制所有元素。单次插入可能触发 O(n) 的复制操作但均摊到每一次插入上花费依然是 O(1)。这类偶尔昂贵、整体平摊的复杂度就是摊还分析里的摊还常数。所以在面试里你可以放心说均摊 O(1)。如果面试官追问为什么不是严格 O(1)就给他讲这两层涨因素体现出你真的理解复杂度来源。空间复杂度是 O(n)数组存储了 n 个元素哈希表存储了 n 对键值映射。4.2 面试官最常追问的五连问问 1为什么不能用 TreeMap 做随机访问 因为 TreeMap 只能按 key 有序遍历要随机取第 k 个元素必须通过类似二分查找第 k 大的方式复杂度 O(log n)。问 2为什么不用 LinkedList LinkedList 头部/尾部插入删除是 O(1)但按值查找需要遍历 O(n)随机访问更是 O(n)两个核心操作都不满足。问 3getRandom 需要保证每个元素概率相同如果数组有空洞怎么办 有了空洞随机抽取就可能抽到无效位概率分布就不对了。这正是我们坚持swap-and-pop来维持数组紧凑性的原因。问 4删除时为什么要把最后一个元素搬过来而不是把后面的元素整体前移 因为整体前移是 O(n)搬最后一个元素是 O(1)。买椟还珠真正要保的是随机访问的 O(1)所以宁可改变数组元素的位置也不能给数组留下空洞。问 5这个结构能不能做到线程安全 现场 HashMap 和 ArrayList 都不是线程安全的。如果多线程并发操作需要加锁或者使用ConcurrentHashMap加显式同步。但加锁后 getRandom 的并发度会受影响分布式场景下甚至要引入更多层设计。这个追问一般出现在系统设计轮能聊到加锁与复制策略基本就过关了。4.3 变体题允许重复元素的 LeetCode 381380 题不允许重复381 题允许重复元素出现多次。核心思想仍然是数组 索引表但索引表要存的不是单个下标而是一组下标。常见的做法是MapInteger, SetIntegervalue 用LinkedHashSet保存该值出现的所有下标。remove 时先从对应 Set 中取出一个下标比如取集合中的第一个然后同样用数组最后一个元素补位同步更新最后一个元素的索引集合最后删除目标下标并弹出数组尾部。这个变体的难点在于删除某个下标后最后一个元素的下标会变成被删除的下标所以要从旧下标集合里同时处理删除旧位置和添补新位置两步。面试时如果能从 380 自然推到 381说明你是真的理解了这套结构而不是背答案。4.4 设计题通用方法论LeetCode 380 属于数据结构设计题。这类题的通用方法论是先把功能需求拆出来再逐个匹配各数据结构的强项最后组合。一般可以按四步走列出所有操作及复杂度要求。为每个操作选择最顺手的数据结构。找出冲突点比如随机访问和快速删除的矛盾。用组合结构消解冲突并处理维护一致性的细节。这个方法不仅适用于 380也适用于 LRU Cache、LFU Cache、LRU with O(1) 等设计题。刷题刷多了你会发现设计题的解法都逃不开分层 索引的组合思路。5. 实操总结与个人体会5.1 刷题中我踩过的真坑我在实际写这道题的时候remove 里的顺序问题真的坑过我。最早的一版 Java 代码是这样写的list.remove(list.size() - 1); map.remove(val);看起来没错但如果删除的不是最后一个元素还有一个关键动作漏掉了没有把last放到被删除的位置上。当时测试用例少前几个 case 踩着过一测到大数组就全乱了。数组里留下一个重复值删除逻辑就飘了。后来我把过程画在纸上模拟了三次删除才真正理解先补位、再删尾、最后删键这条流水线的意义。现在我做这类题习惯先在纸上画出数组和 map 的变化过程尤其是边界条件删第一个、删最后一个、删中间唯一元素、数组只剩一个元素等场景。另外还有一个经验不要一上来就优化代码。先把最朴素的正确版本写出来通过测试后再考虑加不加if (index ! lastIndex)这种判断。我见过不少人一上来就写优化版本反而把自己绕晕。5.2 一个可复制的思路模板如果你现在遇到类似的高频题可以试试这套思维模板哪些操作需要按值找位置 需要的话用哈希表记录值到位置的映射。哪些操作需要按下标访问 需要的话用数组保存元素。删除任意位置元素时能不能换成删除尾部 能用 swap-and-pop 的场景往往就是 O(1) 和 O(n) 的分水岭。每次结构变化后索引表和数组能不能保持一致 这是所有设计题最容易出错的地方。380 就是上述四个问题的最典型答案。把数组存数、哈希存下标刻进脑子里以后做 381、LRU 或者类似的索引类设计题会顺畅很多。5.3 这道题对我后来做系统设计的启发说实话这道题看起来只是刷题但用索引维护位置关系的思想在工程里非常常见。比如数据库主键索引的维护、内存表对随机读场景的优化、游戏服务端对在线玩家集合的随机抽选很多都是数组 哈希表的变体。你甚至可以把它理解成一个极简的内存索引表底层数组保存数据本体哈希表保存逻辑位置。我在做项目迁移的时候也用过类似的策略需要在一张大列表里删除某个元素但不允许整体重排就用尾部元素顶上同时更新所有外部索引引用。这种操作在数据量大的场景下能省下大量拷贝时间。刷题刷到最后学的不是某个具体 API而是一套数据组织思维方式。能从一个 O(1) 的删除技巧联想到真实系统的索引维护才算是真正把题刷明白了。最后再分享一个小习惯每次写完一道设计题都花五分钟问自己一个问题——如果这个结构要维护的字段从一个下标变成一组下标代码要怎么改这个问题能从 380 平移到 381从 381 平移到更复杂的设计场景。我个人的体会是这种递推式的复盘比再多刷十道同类题都更有价值。
