刷力扣链表题大多数人早就习惯了反转链表、合并有序链表那套指针八股冷不丁看到“Linked List Random Node”这种题第一反应往往是愣住链表怎么随机随机一个下标然后走过去还是先遍历一遍把节点存进数组力扣第 382 题就卡在这——它要求你在不知道链表长度、不能复制数组的前提下等概率返回某个节点的值。这题的考点根本不是“你会不会操作链表”而是随机抽样当总数量未知、数据像水流一样源源不断出现时怎么保证每个元素被抽到的概率相等。这也是蓄水池抽样Reservoir Sampling最经典的入门场景。这篇题解笔记既是 382 题的完整 AC 记录也是蓄水池抽样从原理到实现的通俗拆解。适合三类人准备面试时被概率题虐过的人刷题刷到 382 题又嫌题解里“直接套模板”说不清所以然的人以及想在日志采样、随机抽奖场景里用对采样算法的人。读完你会知道概率怎么推导、代码怎么写不会踩坑还能顺手把力扣 398 题也看懂。1. 题目理解与核心思路拆解1.1 题目到底在问什么先看最原始的题目定义。实现一个 Solution 类构造函数传入链表头节点 headgetRandom() 每次调用都要等概率返回链表中的一个节点值。这里有两个关键词值得圈出来。第一个是“等概率”。链表里有 n 个节点那么每个节点被返回的概率都必须是 1/n不能出现头节点概率偏大、尾节点概率偏小的现象。这一点看似理所当然但等你用“边走边决定要不要换”的思路实现时概率往往会歪后面的推导会告诉大家怎么歪的。第二个是“链表”而非“数组”。数组可以用下标做 O(1) 随机访问链表的随机访问是 O(k)走到第 k 个节点需要从头开始遍历。如果先遍历一次数出 length再随机一个下标走第二次功能上没问题时间复杂度 O(n)、空间 O(1)在原题限制下其实并不违规。但问题是力扣官方给的进阶说明有一条很关键——链表长度对算法是不可预知的或者说这道题想考的就是“不依赖 length 的采样方法”。在流式数据场景里length 根本不存在因为数据还在不断追加。这就把思路引向了蓄水池抽样。1.2 为什么“先数长度再随机下标”不够地道我先把丑话说在前面在 382 题本身的环境里先数长度再走一次下标不违反时空复杂度约束也能 AC。很多题解直接嘲讽这种写法“不满足进阶要求”其实是不准确的。真正的差别在于适用场景。假设你的链表是一个静态的、不会再变化的对象比如从配置文件解析出来的列表先求 length 再random.nextInt(length)再遍历完全合理。但假设你在做一个实时日志采样系统日志条目持续追加进链式结构长度每秒都在变或者数据源根本只支持单向遍历一次不能回头访问。此时“数长度”要等数据流结束才数得完而“结束”可能永远不会来。蓄水池抽样的存在意义就是让采样在只遍历一遍、不预知总数量的前提下完成。所以面试官问你“为什么不用 length”你可以回答如果数据是静态可重放的length 方案可以但如果是单次遍历或动态增长的流length 在采样时刻往往不可知蓄水池抽样才是通用解法。这个回答会显得你不是只会套模板而是真理解边界。1.3 题目的进阶要求与隐藏考点原题还有一个容易被忽略的约束不允许使用额外空间。换句话说你不能 new 一个 ArrayList 把所有节点存进去再随机取下标。这个约束直接否掉了“缓存数组”的偷鸡方案逼你在常数空间里完成采样。隐藏考点主要有三个第一是否知道“未知总数下的等概率采样”这个经典问题了解蓄水池抽样第二是否能把“替换概率”写成正确的随机数判断而不是想当然地抽一个全局随机数第三是否能口头证明每个节点概率相等这个证明通常就是面试官要求你手推的环节。很多人准备链表题时只背反转、双指针、快慢指针遇到这道题会突然发现自己的知识盲区。正因为 382 题把链表和概率随机两个主题缝在一起它在面试题库里才一直保持着存在感。2. 蓄水池抽样原理与概率推导2.1 核心思想边走边换越晚越难换蓄水池抽样这个名字听起来唬人核心思想其实很朴素我手里始终拿一个“候选节点”从头到尾遍历链表每遇到一个新节点就以一定概率把手里的旧候选换成新节点。关键是这个概率不是固定的 1/n而是 1/i其中 i 是当前节点的序号。举个例子。看到第 1 个节点手里没别人可选直接拿住它。看到第 2 个节点掷一个二分之一概率的骰子如果中奖就换成第 2 个。看到第 3 个节点掷一个三分之一概率的骰子中奖就换成第 3 个。看到第 4 个换的概率是四分之一。越往后的节点换入的概率越低但你要想越往后的节点被选中后后面需要“扛住”的替换次数也越少。这两股力量一抵消恰好每个节点最终胜出的概率都是 1/n。用生活场景类比班里人数未知老师想“随机叫一个同学回答问题”。老师每看见一个同学都让这个同学站到讲台上然后下一个同学有概率把讲台上的人替换掉。最后一个站在讲台上的人并不是“最幸运的人”而是“运气分配最均匀的人”。这个算法最妙的地方在于它根本不需要知道班里到底有多少人只要人还在进场替换游戏就继续人停了讲台上的人就是均匀随机出来的。2.2 数学推导为什么每个节点概率都是 1/n下面推一遍概率这个推导是面试高频追问建议能默写。设链表长度为 n考虑第 k 个节点1 ≤ k ≤ n最终被返回的概率。它要经历两步第一步轮到第 k 个节点时它要把当前候选替换成自己。因为当前遍历到了第 k 个节点替换概率是 1/k。第二步从第 k1 个节点开始一直到第 n 个节点它们都不能把第 k 个节点替换掉。第 k1 个节点到达时不替换的概率是 1 - 1/(k1) k/(k1)第 k2 个节点到达时不替换概率是 (k1)/(k2)……第 n 个节点到达时不替换概率是 (n-1)/n。把这三部分乘起来P(第 k 个节点最终胜出) (1/k) × (k/(k1)) × ((k1)/(k2)) × ... × ((n-1)/n) 1/n。中间的分子分母全部约掉只剩 1/n。这个结果不依赖 k所以任意一个节点被选中的概率都相等。注意第 1 个节点的情况也满足它胜出概率 1 × 1/2 × 2/3 × ... × (n-1)/n 1/n。这说明算法对“最早到的节点”和“最晚到的节点”一视同仁。2.3 等概率采样不等于“随机一个下标”有一个误区特别普遍把“等概率返回一个节点”等同于“生成一个 0 到 n-1 的随机下标然后走到那个位置”。在数组中这两个说法等价但在链表中不等价。链表没有 O(1) 随机访问更重要的是当链表长度未知时你连“n 的范围”都不知道下标随机无从谈起。蓄水池抽样本质上做了一件事把对“空间位置”的均匀采样转换成了对“到达顺序”的带替换采样。它不再问“这个节点在下标几”而是问“这个节点是第几个到达的我要不要用它替换手里的候选”。顺序信息随着遍历自然获得不需要额外存储。这也是它 O(1) 空间的原因——你只需要记住一个候选值和一个计数器。3. 代码实现与细节优化3.1 Java 写法最标准的蓄水池版本先上最通用的写法。链表非空是前提否则任何随机采样都没有意义。class Solution { private ListNode head; private Random random; public Solution(ListNode head) { this.head head; this.random new Random(); } public int getRandom() { ListNode cur head; int result cur.val; int i 1; while (cur ! null) { // nextInt(i) 返回 [0, i)命中 0 的概率是 1/i if (random.nextInt(i) 0) { result cur.val; } cur cur.next; i; } return result; } }我故意把 result 初始化为 head.val同时循环遍历整个链表。这样第一个节点虽然会被 nextInt(1) 命中因为 nextInt(1) 恒返回 0但替换成 head.val 等于没换逻辑自洽。另一种更省随机数的写法是直接从第二个节点开始public int getRandom() { ListNode cur head.next; int result head.val; int i 2; while (cur ! null) { if (random.nextInt(i) 0) { result cur.val; } cur cur.next; i; } return result; }两种写法结果完全一致。面试时写第一种更稳因为不容易漏掉链表只有单个节点的情况工程里追求少调一次随机数可以用第二种。这里最关键的点是nextInt(i)里的 i 必须正好是当前节点的序号这样命中概率才是 1/i。如果你随便传一个固定值比如nextInt(100)概率就完全错了而且很难通过普通测试发现。3.2 Python 写法随机数边界最容易写错import random class Solution: def __init__(self, head: ListNode): self.head head def getRandom(self) - int: cur self.head result cur.val i 1 while cur: # randint(1, i) 返回 [1, i]命中 i 的概率是 1/i if random.randint(1, i) i: result cur.val cur cur.next i 1 return result这里有个特别容易踩的坑Java 的Random.nextInt(i)是左闭右开区间 [0, i)Python 的random.randint(1, i)是闭区间 [1, i]。所以 Java 判断“命中 0”Python 判断“命中 i”这两个条件概率相同都是 1/i。如果你把 Java 习惯带进 Python写成random.randint(1, i) 0那永远命不中因为返回值最小是 1。反过来在 Java 里写random.nextInt(i) i也永远命不中因为 nextInt(i) 最大只到 i-1。这种错误不会让程序崩溃只会让概率悄悄变歪属于最阴险的 bug。我个人的习惯是在代码注释里直接写明“命中的概率是 1/i”这样即使语言不同检查起来也一目了然。3.3 C 写法与随机数模偏差如果面试官要求 C可以这样写class Solution { ListNode* head; public: Solution(ListNode* head) : head(head) {} int getRandom() { ListNode* cur head; int result head-val; int i 1; while (cur) { if (rand() % i 0) result cur-val; cur cur-next; i; } return result; } };rand() % i是最直接的写法算法题足够用。但要意识到 C 标准库的rand()质量不高周期短、低位分布差而且当 i 不是 RAND_MAX 的因子时存在模偏差余数分布不是完全均匀的。严谨做法是用std::mt19937生成随机数再用均匀分布整数 APIstd::mt19937 rng(std::random_device{}()); std::uniform_int_distributionint dist(0, i - 1); if (dist(rng) 0) result cur-val;面试现场一般不会揪着模偏差不放但你主动说出这一点能体现工程功底。刷题时用rand() % i就行不必过度设计。3.4 复杂度与工程权衡这道题的固有复杂度是getRandom() 时间 O(n)空间 O(1)其中 n 是链表长度。为什么空间 O(1)因为蓄水池大小为 1只需要一个变量存候选值和一个计数器。如果调用 getRandom() 非常频繁例如每秒十万次而链表又很长那每次 O(n) 全遍历会很难受。工程上的常见策略是折中如果链表内容在构造后不再改变且内存允许可以在构造函数里一次性把节点值复制到数组getRandom() 变成 O(1) 随机下标。这就是用空间换时间。但它违反 382 题的进阶精神所以刷题时不要提交这个版本只能作为工程讨论提出来。反过来如果链表本身是动态增长的比如实时日志链表缓存数组每次新增节点都要同步更新成本不可控蓄水池就成了唯一自然的选择。遇到实际需求时先问自己三个问题数据会不会变内存是不是瓶颈调用频率有多高答案不同选型完全不同。4. 验证、测试与常见坑4.1 蒙特卡洛验证十万次跑出来看分布算法题里概率相关的代码最怕的是“逻辑看着对概率其实歪了”。这时候盲目的单元测试帮不上忙因为单次调用只有正确/错误之分看不出来分布。我的习惯是写一个蒙特卡洛验证脚本构造一个长度为 3 的链表 [1, 2, 3]调用 getRandom() 十万次统计每个值的出现次数看是不是接近 1:1:1。from collections import Counter import random def reservoir_sample(arr): result arr[0] for i in range(2, len(arr) 1): if random.randint(1, i) i: result arr[i - 1] return result cnt Counter() for _ in range(100000): cnt[reservoir_sample([1, 2, 3])] 1 print(cnt) # 期望每个 key 出现约 33333 次跑出来大概是Counter({1: 33378, 2: 33281, 3: 33341})这种样子的波动。如果某个值稳定低于 33000 或者高于 34000说明概率边界写错了。当 n 变大时可以用卡方检验做更严格判定但刷题看比例足够。这个验证法对后面所有概率相关题目都通用我强烈建议学会。4.2 五类翻车现场我见过甚至自己踩过第一随机数边界写错这是最高频的坑上一节已经详细说过。核心就是记住每个语言随机 API 的闭开区间。第二计数器从 0 开始计数却直接拿去给nextInt()。Java 的nextInt(0)会抛IllegalArgumentException因为参数必须是正数。正确做法是 i 从 1 开始遇到第一个节点就是 1。第三while 循环条件写成while (head ! null)然后循环体里对 head 做推进把构造时保存的链表头搞丢了。第一次调用 getRandom() 正常第二次开始就从 null 或半个链表开始遍历结果跟随机没关系了。正确做法是声明一个局部变量 cur 来遍历。第四返回值类型写错。题目要求返回节点值 int不是返回 ListNode。这道题里 head.val 是结果head 本身不是结果。低级错误但面试紧张时会犯。第五误以为“换得越晚概率越高”把替换概率写成 (i-1)/i 而不是 1/i导致尾部节点被疯狂换走概率变成前重后轻。这需要对上一节的概率推导有直觉否则真会调反。4.3 多线程场景下的随机数处理如果 getRandom() 被多个线程同时调用要注意两个线程不能共享同一个有状态的 Random 对象而引发竞争。Java 的java.util.Random是线程安全的内部通过 CAS 更新种子不会出错但可能因为竞争让性能下降。高并发下可以用ThreadLocalRandom.current().nextInt(i)每个线程用自己的随机数生成器性能更好。Python 的random模块线程安全程度也够用但这个深度刷题时不太会被问到。还有一个细节很多人纠结要不要用 SecureRandom。如果这个随机结果涉及抽奖、资金等安全敏感场景强烈建议换成密码学安全随机源。但刷题或者普通日志采样Random完全够用。工程里的随机数选型按“安全性要求”分三档普通随机用 Random高并发用 ThreadLocalRandom安全敏感用 SecureRandom。4.4 为什么不能先随机一个数再从头走一次我知道还有人想这样写先遍历一遍数长度 n再random.nextInt(n)再从头走到随机位置返回。这个写法在静态链表下完全正确时间复杂度 O(n)空间 O(1)甚至能通过力扣的判题。但面试官大概率会追问“如果链表长度你不知道呢如果这是一个流呢”蓄水池抽样最大的价值恰恰是它连“数长度”这一步都不需要。当你手持一个 head 开始遍历时你同时在做两件事采集数据、做随机替换。数据到底有多少个是遍历结束之后才知道的但采样结果在遍历结束那一刻已经均匀生成了。这种“身上不带全局信息也能做出全局均匀决策”的特性才是它成为数据流经典算法的原因。5. 扩展蓄水池抽样与力扣同型题5.1 从取 1 个到取 K 个通用蓄水池382 题是蓄水池抽样最简单的 k1 形式但面试官可能顺手把问题改成“从链表中等概率抽取 3 个节点”或“从数据流中等概率保留 5 个样本”。通用算法也很简单先把前 K 个元素放入蓄水池数组。从第 K1 个元素起遍历到第 i 个元素时以 K/i 的概率决定是否要替换池中元素如果要替换在池中均匀随机挑一个位置把新元素放进去。概率证明的思路和 k1 完全一样第 i 个元素最终留在池中的概率化简后等于 K/n。推到这一步后你可以把 382 题的代码从“一个候选变量”扩展成“一个长度为 K 的数组”复杂度变成时间 O(n)空间 O(K)。这个扩展版在工程里更常见因为很多时候你需要的不是随机挑 1 个而是随机留 N 个样本。5.2 力扣里和蓄水池抽样相关的题我刷题时喜欢把同类型的题放在一起看这样知识点能串成体系。跟 382 题相关的力扣题至少有几道题目核心思路知识点382 Linked List Random Node链表等概率取 1 个蓄水池抽样 k1398 Random Pick Index数组等概率取 target 下标蓄水池抽样528 Random Pick with Weight权重随机前缀和 二分470 Implement Rand10() Using Rand7()用 Rand7 构造 Rand10拒绝采样398 题是 382 题的近亲给定数组和 target要求等概率返回任意一个值为 target 的下标但 target 的出现次数不确定所以又落到蓄水池抽样上。528 和 470 虽然不直接是同一种算法但它们都属于“随机采样”这个知识域。把这几道放在一起刷你会慢慢形成概率题的解题直觉要么蓄水池要么前缀和加权要么拒绝采样。先判断场景再套工具比东一榔头西一棒子有效得多。5.3 工程里的真实应用日志采样、抽奖、AB 实验蓄水池抽样不是只活在算法题里。我实际见过的场景有几种。一是日志系统抽样分析。系统每秒产生大量日志总量不可预知你想均匀抽 1% 或者固定抽 N 条做离线分析。把每条日志当成链表的一个节点蓄水池算法可以在扫描日志流的同时留下均匀样本不用等日志流结束。二是抽奖活动。活动期间参与人数不断变化结束后才知道总人数但你想在活动进行中就能随时公布“当前已经随机抽出的中奖者”。对每个新参与用户执行 1/i 替换逻辑最终就是等概率中奖。三是 AB 实验的分流。当用户群体以流式到达且分组比例恒定需要保证每个用户进入实验组或对照组的概率稳定加权蓄水池抽样及其变体会派上用场。这个场景比刷题复杂但核心思想一脉相承。这道 382 题我前前后后刷过不止一遍每遍都有新体会。第一次只是把代码背下来第二次推概率推导第三次才真正想明白“为什么不知道 n 也能均匀采样”。如果非要说有什么刷题建议我的经验是遇到这种概率题不要只盯着 AC多问自己一句“如果数据没有终点这个算法还成立吗”。蓄水池抽样最迷人的地方就是它把“全局均匀”这件事用常数空间和一次遍历就解决了。最后再分享一个小习惯凡是随机相关代码我都喜欢用蒙特卡洛脚本验证十几次眼见为实比嘴上的推导直观多了。希望这篇题解能帮你少走点弯路。
蓄水池抽样详解：力扣382题链表随机节点等概率采样
刷力扣链表题大多数人早就习惯了反转链表、合并有序链表那套指针八股冷不丁看到“Linked List Random Node”这种题第一反应往往是愣住链表怎么随机随机一个下标然后走过去还是先遍历一遍把节点存进数组力扣第 382 题就卡在这——它要求你在不知道链表长度、不能复制数组的前提下等概率返回某个节点的值。这题的考点根本不是“你会不会操作链表”而是随机抽样当总数量未知、数据像水流一样源源不断出现时怎么保证每个元素被抽到的概率相等。这也是蓄水池抽样Reservoir Sampling最经典的入门场景。这篇题解笔记既是 382 题的完整 AC 记录也是蓄水池抽样从原理到实现的通俗拆解。适合三类人准备面试时被概率题虐过的人刷题刷到 382 题又嫌题解里“直接套模板”说不清所以然的人以及想在日志采样、随机抽奖场景里用对采样算法的人。读完你会知道概率怎么推导、代码怎么写不会踩坑还能顺手把力扣 398 题也看懂。1. 题目理解与核心思路拆解1.1 题目到底在问什么先看最原始的题目定义。实现一个 Solution 类构造函数传入链表头节点 headgetRandom() 每次调用都要等概率返回链表中的一个节点值。这里有两个关键词值得圈出来。第一个是“等概率”。链表里有 n 个节点那么每个节点被返回的概率都必须是 1/n不能出现头节点概率偏大、尾节点概率偏小的现象。这一点看似理所当然但等你用“边走边决定要不要换”的思路实现时概率往往会歪后面的推导会告诉大家怎么歪的。第二个是“链表”而非“数组”。数组可以用下标做 O(1) 随机访问链表的随机访问是 O(k)走到第 k 个节点需要从头开始遍历。如果先遍历一次数出 length再随机一个下标走第二次功能上没问题时间复杂度 O(n)、空间 O(1)在原题限制下其实并不违规。但问题是力扣官方给的进阶说明有一条很关键——链表长度对算法是不可预知的或者说这道题想考的就是“不依赖 length 的采样方法”。在流式数据场景里length 根本不存在因为数据还在不断追加。这就把思路引向了蓄水池抽样。1.2 为什么“先数长度再随机下标”不够地道我先把丑话说在前面在 382 题本身的环境里先数长度再走一次下标不违反时空复杂度约束也能 AC。很多题解直接嘲讽这种写法“不满足进阶要求”其实是不准确的。真正的差别在于适用场景。假设你的链表是一个静态的、不会再变化的对象比如从配置文件解析出来的列表先求 length 再random.nextInt(length)再遍历完全合理。但假设你在做一个实时日志采样系统日志条目持续追加进链式结构长度每秒都在变或者数据源根本只支持单向遍历一次不能回头访问。此时“数长度”要等数据流结束才数得完而“结束”可能永远不会来。蓄水池抽样的存在意义就是让采样在只遍历一遍、不预知总数量的前提下完成。所以面试官问你“为什么不用 length”你可以回答如果数据是静态可重放的length 方案可以但如果是单次遍历或动态增长的流length 在采样时刻往往不可知蓄水池抽样才是通用解法。这个回答会显得你不是只会套模板而是真理解边界。1.3 题目的进阶要求与隐藏考点原题还有一个容易被忽略的约束不允许使用额外空间。换句话说你不能 new 一个 ArrayList 把所有节点存进去再随机取下标。这个约束直接否掉了“缓存数组”的偷鸡方案逼你在常数空间里完成采样。隐藏考点主要有三个第一是否知道“未知总数下的等概率采样”这个经典问题了解蓄水池抽样第二是否能把“替换概率”写成正确的随机数判断而不是想当然地抽一个全局随机数第三是否能口头证明每个节点概率相等这个证明通常就是面试官要求你手推的环节。很多人准备链表题时只背反转、双指针、快慢指针遇到这道题会突然发现自己的知识盲区。正因为 382 题把链表和概率随机两个主题缝在一起它在面试题库里才一直保持着存在感。2. 蓄水池抽样原理与概率推导2.1 核心思想边走边换越晚越难换蓄水池抽样这个名字听起来唬人核心思想其实很朴素我手里始终拿一个“候选节点”从头到尾遍历链表每遇到一个新节点就以一定概率把手里的旧候选换成新节点。关键是这个概率不是固定的 1/n而是 1/i其中 i 是当前节点的序号。举个例子。看到第 1 个节点手里没别人可选直接拿住它。看到第 2 个节点掷一个二分之一概率的骰子如果中奖就换成第 2 个。看到第 3 个节点掷一个三分之一概率的骰子中奖就换成第 3 个。看到第 4 个换的概率是四分之一。越往后的节点换入的概率越低但你要想越往后的节点被选中后后面需要“扛住”的替换次数也越少。这两股力量一抵消恰好每个节点最终胜出的概率都是 1/n。用生活场景类比班里人数未知老师想“随机叫一个同学回答问题”。老师每看见一个同学都让这个同学站到讲台上然后下一个同学有概率把讲台上的人替换掉。最后一个站在讲台上的人并不是“最幸运的人”而是“运气分配最均匀的人”。这个算法最妙的地方在于它根本不需要知道班里到底有多少人只要人还在进场替换游戏就继续人停了讲台上的人就是均匀随机出来的。2.2 数学推导为什么每个节点概率都是 1/n下面推一遍概率这个推导是面试高频追问建议能默写。设链表长度为 n考虑第 k 个节点1 ≤ k ≤ n最终被返回的概率。它要经历两步第一步轮到第 k 个节点时它要把当前候选替换成自己。因为当前遍历到了第 k 个节点替换概率是 1/k。第二步从第 k1 个节点开始一直到第 n 个节点它们都不能把第 k 个节点替换掉。第 k1 个节点到达时不替换的概率是 1 - 1/(k1) k/(k1)第 k2 个节点到达时不替换概率是 (k1)/(k2)……第 n 个节点到达时不替换概率是 (n-1)/n。把这三部分乘起来P(第 k 个节点最终胜出) (1/k) × (k/(k1)) × ((k1)/(k2)) × ... × ((n-1)/n) 1/n。中间的分子分母全部约掉只剩 1/n。这个结果不依赖 k所以任意一个节点被选中的概率都相等。注意第 1 个节点的情况也满足它胜出概率 1 × 1/2 × 2/3 × ... × (n-1)/n 1/n。这说明算法对“最早到的节点”和“最晚到的节点”一视同仁。2.3 等概率采样不等于“随机一个下标”有一个误区特别普遍把“等概率返回一个节点”等同于“生成一个 0 到 n-1 的随机下标然后走到那个位置”。在数组中这两个说法等价但在链表中不等价。链表没有 O(1) 随机访问更重要的是当链表长度未知时你连“n 的范围”都不知道下标随机无从谈起。蓄水池抽样本质上做了一件事把对“空间位置”的均匀采样转换成了对“到达顺序”的带替换采样。它不再问“这个节点在下标几”而是问“这个节点是第几个到达的我要不要用它替换手里的候选”。顺序信息随着遍历自然获得不需要额外存储。这也是它 O(1) 空间的原因——你只需要记住一个候选值和一个计数器。3. 代码实现与细节优化3.1 Java 写法最标准的蓄水池版本先上最通用的写法。链表非空是前提否则任何随机采样都没有意义。class Solution { private ListNode head; private Random random; public Solution(ListNode head) { this.head head; this.random new Random(); } public int getRandom() { ListNode cur head; int result cur.val; int i 1; while (cur ! null) { // nextInt(i) 返回 [0, i)命中 0 的概率是 1/i if (random.nextInt(i) 0) { result cur.val; } cur cur.next; i; } return result; } }我故意把 result 初始化为 head.val同时循环遍历整个链表。这样第一个节点虽然会被 nextInt(1) 命中因为 nextInt(1) 恒返回 0但替换成 head.val 等于没换逻辑自洽。另一种更省随机数的写法是直接从第二个节点开始public int getRandom() { ListNode cur head.next; int result head.val; int i 2; while (cur ! null) { if (random.nextInt(i) 0) { result cur.val; } cur cur.next; i; } return result; }两种写法结果完全一致。面试时写第一种更稳因为不容易漏掉链表只有单个节点的情况工程里追求少调一次随机数可以用第二种。这里最关键的点是nextInt(i)里的 i 必须正好是当前节点的序号这样命中概率才是 1/i。如果你随便传一个固定值比如nextInt(100)概率就完全错了而且很难通过普通测试发现。3.2 Python 写法随机数边界最容易写错import random class Solution: def __init__(self, head: ListNode): self.head head def getRandom(self) - int: cur self.head result cur.val i 1 while cur: # randint(1, i) 返回 [1, i]命中 i 的概率是 1/i if random.randint(1, i) i: result cur.val cur cur.next i 1 return result这里有个特别容易踩的坑Java 的Random.nextInt(i)是左闭右开区间 [0, i)Python 的random.randint(1, i)是闭区间 [1, i]。所以 Java 判断“命中 0”Python 判断“命中 i”这两个条件概率相同都是 1/i。如果你把 Java 习惯带进 Python写成random.randint(1, i) 0那永远命不中因为返回值最小是 1。反过来在 Java 里写random.nextInt(i) i也永远命不中因为 nextInt(i) 最大只到 i-1。这种错误不会让程序崩溃只会让概率悄悄变歪属于最阴险的 bug。我个人的习惯是在代码注释里直接写明“命中的概率是 1/i”这样即使语言不同检查起来也一目了然。3.3 C 写法与随机数模偏差如果面试官要求 C可以这样写class Solution { ListNode* head; public: Solution(ListNode* head) : head(head) {} int getRandom() { ListNode* cur head; int result head-val; int i 1; while (cur) { if (rand() % i 0) result cur-val; cur cur-next; i; } return result; } };rand() % i是最直接的写法算法题足够用。但要意识到 C 标准库的rand()质量不高周期短、低位分布差而且当 i 不是 RAND_MAX 的因子时存在模偏差余数分布不是完全均匀的。严谨做法是用std::mt19937生成随机数再用均匀分布整数 APIstd::mt19937 rng(std::random_device{}()); std::uniform_int_distributionint dist(0, i - 1); if (dist(rng) 0) result cur-val;面试现场一般不会揪着模偏差不放但你主动说出这一点能体现工程功底。刷题时用rand() % i就行不必过度设计。3.4 复杂度与工程权衡这道题的固有复杂度是getRandom() 时间 O(n)空间 O(1)其中 n 是链表长度。为什么空间 O(1)因为蓄水池大小为 1只需要一个变量存候选值和一个计数器。如果调用 getRandom() 非常频繁例如每秒十万次而链表又很长那每次 O(n) 全遍历会很难受。工程上的常见策略是折中如果链表内容在构造后不再改变且内存允许可以在构造函数里一次性把节点值复制到数组getRandom() 变成 O(1) 随机下标。这就是用空间换时间。但它违反 382 题的进阶精神所以刷题时不要提交这个版本只能作为工程讨论提出来。反过来如果链表本身是动态增长的比如实时日志链表缓存数组每次新增节点都要同步更新成本不可控蓄水池就成了唯一自然的选择。遇到实际需求时先问自己三个问题数据会不会变内存是不是瓶颈调用频率有多高答案不同选型完全不同。4. 验证、测试与常见坑4.1 蒙特卡洛验证十万次跑出来看分布算法题里概率相关的代码最怕的是“逻辑看着对概率其实歪了”。这时候盲目的单元测试帮不上忙因为单次调用只有正确/错误之分看不出来分布。我的习惯是写一个蒙特卡洛验证脚本构造一个长度为 3 的链表 [1, 2, 3]调用 getRandom() 十万次统计每个值的出现次数看是不是接近 1:1:1。from collections import Counter import random def reservoir_sample(arr): result arr[0] for i in range(2, len(arr) 1): if random.randint(1, i) i: result arr[i - 1] return result cnt Counter() for _ in range(100000): cnt[reservoir_sample([1, 2, 3])] 1 print(cnt) # 期望每个 key 出现约 33333 次跑出来大概是Counter({1: 33378, 2: 33281, 3: 33341})这种样子的波动。如果某个值稳定低于 33000 或者高于 34000说明概率边界写错了。当 n 变大时可以用卡方检验做更严格判定但刷题看比例足够。这个验证法对后面所有概率相关题目都通用我强烈建议学会。4.2 五类翻车现场我见过甚至自己踩过第一随机数边界写错这是最高频的坑上一节已经详细说过。核心就是记住每个语言随机 API 的闭开区间。第二计数器从 0 开始计数却直接拿去给nextInt()。Java 的nextInt(0)会抛IllegalArgumentException因为参数必须是正数。正确做法是 i 从 1 开始遇到第一个节点就是 1。第三while 循环条件写成while (head ! null)然后循环体里对 head 做推进把构造时保存的链表头搞丢了。第一次调用 getRandom() 正常第二次开始就从 null 或半个链表开始遍历结果跟随机没关系了。正确做法是声明一个局部变量 cur 来遍历。第四返回值类型写错。题目要求返回节点值 int不是返回 ListNode。这道题里 head.val 是结果head 本身不是结果。低级错误但面试紧张时会犯。第五误以为“换得越晚概率越高”把替换概率写成 (i-1)/i 而不是 1/i导致尾部节点被疯狂换走概率变成前重后轻。这需要对上一节的概率推导有直觉否则真会调反。4.3 多线程场景下的随机数处理如果 getRandom() 被多个线程同时调用要注意两个线程不能共享同一个有状态的 Random 对象而引发竞争。Java 的java.util.Random是线程安全的内部通过 CAS 更新种子不会出错但可能因为竞争让性能下降。高并发下可以用ThreadLocalRandom.current().nextInt(i)每个线程用自己的随机数生成器性能更好。Python 的random模块线程安全程度也够用但这个深度刷题时不太会被问到。还有一个细节很多人纠结要不要用 SecureRandom。如果这个随机结果涉及抽奖、资金等安全敏感场景强烈建议换成密码学安全随机源。但刷题或者普通日志采样Random完全够用。工程里的随机数选型按“安全性要求”分三档普通随机用 Random高并发用 ThreadLocalRandom安全敏感用 SecureRandom。4.4 为什么不能先随机一个数再从头走一次我知道还有人想这样写先遍历一遍数长度 n再random.nextInt(n)再从头走到随机位置返回。这个写法在静态链表下完全正确时间复杂度 O(n)空间 O(1)甚至能通过力扣的判题。但面试官大概率会追问“如果链表长度你不知道呢如果这是一个流呢”蓄水池抽样最大的价值恰恰是它连“数长度”这一步都不需要。当你手持一个 head 开始遍历时你同时在做两件事采集数据、做随机替换。数据到底有多少个是遍历结束之后才知道的但采样结果在遍历结束那一刻已经均匀生成了。这种“身上不带全局信息也能做出全局均匀决策”的特性才是它成为数据流经典算法的原因。5. 扩展蓄水池抽样与力扣同型题5.1 从取 1 个到取 K 个通用蓄水池382 题是蓄水池抽样最简单的 k1 形式但面试官可能顺手把问题改成“从链表中等概率抽取 3 个节点”或“从数据流中等概率保留 5 个样本”。通用算法也很简单先把前 K 个元素放入蓄水池数组。从第 K1 个元素起遍历到第 i 个元素时以 K/i 的概率决定是否要替换池中元素如果要替换在池中均匀随机挑一个位置把新元素放进去。概率证明的思路和 k1 完全一样第 i 个元素最终留在池中的概率化简后等于 K/n。推到这一步后你可以把 382 题的代码从“一个候选变量”扩展成“一个长度为 K 的数组”复杂度变成时间 O(n)空间 O(K)。这个扩展版在工程里更常见因为很多时候你需要的不是随机挑 1 个而是随机留 N 个样本。5.2 力扣里和蓄水池抽样相关的题我刷题时喜欢把同类型的题放在一起看这样知识点能串成体系。跟 382 题相关的力扣题至少有几道题目核心思路知识点382 Linked List Random Node链表等概率取 1 个蓄水池抽样 k1398 Random Pick Index数组等概率取 target 下标蓄水池抽样528 Random Pick with Weight权重随机前缀和 二分470 Implement Rand10() Using Rand7()用 Rand7 构造 Rand10拒绝采样398 题是 382 题的近亲给定数组和 target要求等概率返回任意一个值为 target 的下标但 target 的出现次数不确定所以又落到蓄水池抽样上。528 和 470 虽然不直接是同一种算法但它们都属于“随机采样”这个知识域。把这几道放在一起刷你会慢慢形成概率题的解题直觉要么蓄水池要么前缀和加权要么拒绝采样。先判断场景再套工具比东一榔头西一棒子有效得多。5.3 工程里的真实应用日志采样、抽奖、AB 实验蓄水池抽样不是只活在算法题里。我实际见过的场景有几种。一是日志系统抽样分析。系统每秒产生大量日志总量不可预知你想均匀抽 1% 或者固定抽 N 条做离线分析。把每条日志当成链表的一个节点蓄水池算法可以在扫描日志流的同时留下均匀样本不用等日志流结束。二是抽奖活动。活动期间参与人数不断变化结束后才知道总人数但你想在活动进行中就能随时公布“当前已经随机抽出的中奖者”。对每个新参与用户执行 1/i 替换逻辑最终就是等概率中奖。三是 AB 实验的分流。当用户群体以流式到达且分组比例恒定需要保证每个用户进入实验组或对照组的概率稳定加权蓄水池抽样及其变体会派上用场。这个场景比刷题复杂但核心思想一脉相承。这道 382 题我前前后后刷过不止一遍每遍都有新体会。第一次只是把代码背下来第二次推概率推导第三次才真正想明白“为什么不知道 n 也能均匀采样”。如果非要说有什么刷题建议我的经验是遇到这种概率题不要只盯着 AC多问自己一句“如果数据没有终点这个算法还成立吗”。蓄水池抽样最迷人的地方就是它把“全局均匀”这件事用常数空间和一次遍历就解决了。最后再分享一个小习惯凡是随机相关代码我都喜欢用蒙特卡洛脚本验证十几次眼见为实比嘴上的推导直观多了。希望这篇题解能帮你少走点弯路。
