LeetCode 上刷到第 398 题 Random Pick Index 时我第一反应是这不就是给个数组随机返回一个目标值的下标嘛等真正写完提交才发现里面藏着概率均匀性和空间取舍两个考点。这道题在热门 100 题和各家面试题单里出镜率都不低很多人背过答案但被追问一句“为什么每个下标概率一样”就卡住。这篇博客就把这道题从题目到工程完全拆开重点讲清楚蓄水池抽样Reservoir Sampling的来龙去脉以及哈希表方案和蓄水池方案该怎么选。1. 一眼看穿题目本质随机、均匀、索引1.1 题目还原与表面难度题目本身一句话就能说清给定一个整数数组nums和一个目标值target要求返回target在数组中出现的任意一个下标但每个下标被返回的概率必须相等。举个例子如果nums [1, 2, 3, 3, 3]pick(3)可能有 2、3、4 三种结果每种概率都应该是 1/3而pick(1)只能返回 0pick(2)只能返回 1。很多第一次刷到这题的人包括我第一反应都是这还用想随机生成一个下标判断nums[i]是不是 target 不就行了等真正去写坑就来了。如果只在第一次匹配到 target 时返回每次 pick 得到的是固定下标完全不随机如果先遍历一遍收集所有 target 下标再随机选一个这确实能过但并非最优解尤其是在nums非常大、pick调用频繁的场景下内存和时间都会成为问题。LeetCode 上这题的标签里挂着 Reservoir Sampling蓄水池抽样这才是这道题真正想考察的点。也就是说它表面是一道“随机返回索引”的模拟题本质是一道概率题加流式数据处理题。要真正掌握这题需要弄明白三件事一是如何保证“每个下标概率相等”这个约束二是当数据规模变大时空间复杂度能不能降下来三是随机函数的选取会不会引入概率偏差。这三件事也就是这题的三个隐藏考点。1.2 三个隐藏考点第一个隐藏考点是概率均匀性。很多人会用rand() % k来选择下标其中 k 是 target 出现的次数。在 k 比较小的时候rand() % k的概率分布大体均匀但严格来说如果 RAND_MAX 1 不能被 k 整除余数较小的几个数出现概率会略微偏高。这种偏差在题目给的测试用例里几乎测不出来但在工程场景下可能会导致抽样结果有偏。严谨的写法应该用 C11 的random库里的uniform_int_distribution而不是裸的rand()。第二个隐藏考点是空间复杂度。哈希表方案先把所有下标存进unordered_mappick 时直接随机取。预处理 O(n)、pick O(1)单个用例跑得飞快。但数组有十万、百万个元素时每个元素都要存进哈希表内存开销一下就上去了。而蓄水池抽样方案只保存nums本身pick 时从头扫一遍O(n) 时间和 O(1) 空间搞定。面试官问“如果这数组不是一次性给全而是像一个数据流一样源源不断过来你怎么做”你会发现哈希表需要预知完整数据而蓄水池抽样天然适合流式环境。第三个隐藏考点是代码的边界处理。比如 target 不在数组里怎么办虽然题目默认 target 一定存在但工程上要处理再比如数组为空怎么办pick 一个不存在的值会不会越界还有随机数为 0 时如何判断连续多次 pick 会不会用到上一次的状态。这些细节往往是 LeetCode 提交时 WA 和 RE 的根源。理解了这三个点再往下看两种解法就会清楚很多。2. 解法一哈希表缓存全部下标空间换时间2.1 实现思路与C代码哈希表方案的思路非常直接在构造函数里遍历一次nums建立一个从数值到下标数组的映射。之后每次调pick(target)只需要从哈希表里找到 target 对应的下标数组然后用随机数生成一个下标返回该下标即可。这个方案的代码量极小逻辑也最简单适合作为第一版实现快速通过题目。class Solution { private: unordered_mapint, vectorint positions; public: Solution(vectorint nums) { for (int i 0; i nums.size(); i) { positions[nums[i]].push_back(i); } } int pick(int target) { const vectorint v positions[target]; int idx rand() % v.size(); return v[idx]; } };这段代码有个细节unordered_map的operator[]如果 target 不存在会自动插入一个空 vector所以直接用没问题。但注意v.size()返回的是size_trand() % v.size()的结果也是size_t把它赋给 int 时如果 vector 很小没问题极端情况下size_t超过 int 范围会有隐患但通常不会发生。更安全的写法是先缓存 size用 int 类型或者直接让 idx 为size_t然后强转。另外使用rand()前不需要srandLeetCode 的评测环境会自动处理但本地调试时最好srand(time(nullptr))否则每次运行随机序列固定看不出概率特性。这个版本很好理解唯一要提醒的是positions[target]这里会复制吗不会。我用了const vectorint v绑定到哈希表里的 vector不会拷贝。如果写成auto v positions[target]那就是复制target 出现次数多时会拖慢 pick。这点细节值得注意。2.2 时间和空间复杂度哈希表方案的复杂度很好算。构造函数里遍历数组时间复杂度 O(n)空间复杂度 O(n)因为每个元素的下标都存了一份。pick 方法里先查哈希表 O(1)再取随机数 O(1)从 vector 按下标取元素 O(1)所以整体 O(1)。这个复杂度在 LeetCode 上表现很好通常几十毫秒就能通过。但要注意这里的“pick O(1)”是摊还意义上的严格说还需要随机数生成器的开销。如果使用uniform_int_distribution构造分布对象和生成一次随机数也是 O(1)。在实际测试中当 target 重复次数特别多比如一个长度为 10^5 的数组里全是同一个数哈希表方案 pick 时是对长度为 10^5 的 vector 求一个随机下标这没问题而蓄水池方案 pick 时要从头扫完这 10^5 个元素耗时明显。所以光看 LeetCode 的提交哈希表方案可能会更快。但是空间上的代价是实打实的每个下标存成一个 int假设 int 4 字节再加上unordered_map的桶开销和 vector 的扩容开销实际内存可能是原始数组的好几倍。如果nums是 100 万元素哈希表方案可能吃几百 MB 内存而蓄水池方案只需要保存 nums 本身约 4 MB。这就是两者最大的分水岭。2.3 适用边界与内存隐患所以哈希表方案适合什么场景适合 nums 不算太大且 pick 调用非常频繁的场景。比如内存足够一个服务启动后加载固定配置里面是一堆 ID 到索引的映射后续大量查询随机索引用哈希表能保证每个 pick 都是 O(1)吞吐量高。反过来如果 nums 是一个超大文件的映射或者是一个无限数据流哈希表方案就直接跪了因为你要么存不下要么根本等不到完整数据。另外还有一个隐藏问题原题中构造函数的输入 nums 后续被视为“不可变”但工程上如果允许数组更新哈希表里的下标会失效。比如数组某个位置的值改了你需要同步更新哈希表这在高频更新场景下很麻烦。而蓄水池方案每次 pick 都读数组当前值天然支持数据变化。所以回答这类问题时要先跟面试官确认“数组是否只读”“能否用额外空间”再决定用哪种方案。这也能体现沟通意识。我自己的建议是刷题阶段两种方案都写一遍先哈希表确保会做题再蓄水池确保懂原理。面试时如果实在想不出蓄水池先把哈希表方案讲出来再主动提一句“如果能接受 O(n) 空间这个最简单如果要求 O(1) 空间或者流式输入可以用蓄水池抽样”瞬间会让面试官觉得你有工程大局观。3. 解法二蓄水池抽样的单候选版省空间又优雅3.1 蓄水池抽样核心原理蓄水池抽样是一类经典随机算法。最常见的问题是这样有一个长度未知的数据流你想从中等概率地随机抽取 k 个元素但你不能把所有数据都读进内存只能遍历一次。算法很简单先把前 k 个元素放进“蓄水池”从第 k1 个元素开始第 i 个元素以 k/i 的概率决定是否替换蓄水池中的某个元素遍历结束后蓄水池里的 k 个元素就是均匀随机样本。当 k1 时算法退化成“单候选”版本遇到第 i 个元素时以 1/i 的概率把它设为当前候选否则保留原来的候选。这个算法保证每个元素最终被选中的概率都是 1/n。它的美妙之处在于你完全不需要知道 n 是多少也不知道后面还有多少元素只用一个变量存候选一个变量计个数就能得到等概率随机样本。LeetCode 398 正是 k1 蓄水池抽样的应用。注意这里的“数据流”不是整个 nums而是“值为 target 的那些下标”构成的流。你不能提前知道 target 一共出现几次但可以通过遍历 nums 时遇到一个 target 就数一个把每个匹配位置当作流中的一个元素。第 i 个匹配位置出现的概率就是 1/i最终每个匹配位置被选中的概率是 1/k正好符合题目要求。3.2 应用到398题的代码实现按照蓄水池抽样的思路pick 方法应该这样写每次调用时从下标 0 开始遍历 nums维护 count 记录已经遇到了几个值等于 target 的元素每遇到一个 targetcount 加一然后生成一个[0, count-1]的随机整数 r如果 r 0就把当前下标设为 result。遍历完整个数组后返回 result。注意 count 和 result 都必须是 pick 内的局部变量不能把它们放到类的成员变量里“累加”否则上一次 pick 的状态会污染下一次。class Solution { private: vectorint nums; public: Solution(vectorint nums) : nums(nums) {} int pick(int target) { int result -1; int count 0; for (int i 0; i nums.size(); i) { if (nums[i] target) { count; // 以 1/count 的概率替换 result if (rand() % count 0) { result i; } } } return result; } };这里的rand() % count 0表示随机数等于 0概率是 1/count。例如 count 为 3rand()%3的结果为 0、1、2 各 1/3 概率只有结果为 0 时替换所以新元素被选中的概率正好是 1/3。这个写法的优点是简洁缺点是rand()%count有轻微的 modulo bias在严格场景可以用uniform_int_distributionstd::random_device rd; std::mt19937 gen(rd()); ... if (std::uniform_int_distributionint(0, count - 1)(gen) 0) { result i; }LeetCode 的判题用例比较宽松用 rand() 也能通过只是面试时最好提一嘴更优实现。但要注意std::random_device和mt19937最好定义为类成员或 static避免每次 pick 都重新生成引擎那样会浪费资源也可能影响随机性。3.3 等概率性的数学证明为什么这个简单算法能保证每个 target 下标被选中的概率都是 1/k我们用数学归纳法来证明。假设 target 一共出现了 k 次下标依次记为 t1, t2, ..., tk。处理到 ti 时它被替换进 result 的概率是 1/i。问题是后面 tjj i还有可能替换掉它所以 ti 最终成为 result 的概率等于“ti 被选中”且“后续所有 tj 都不替换它”的概率。后续每个 tj 替换 result 的概率是 1/j不替换的概率是1 - 1/j (j-1)/j。把这些概率乘起来P(ti 最终被选中) (1/i) × (i/(i1)) × ((i1)/(i2)) × ... × ((k-1)/k) 1/k。这个连乘中从第二项开始分子分母交错相消最后只剩 1/k。所以不管是第 1 次出现的 target 还是第 k 次出现的 target最终被选中的概率完全一样都是 1/k。这就是蓄水池抽样最核心的数学保证。这个证明依赖于每次替换的独立随机性所以每次调用 random 都必须重新生成不能用一个固定的随机序列。3.4 实现时容易翻车的三个细节细节一随机数条件的写法。有些同学会写if (rand() / RAND_MAX 1.0 / count)这样会引入浮点比较而且rand() / RAND_MAX在整数除法下直接恒为 0导致永远不替换。正确做法是取模判断或者用整数随机分布。细节二count 的语义。count 只统计 target 出现的次数不是遍历下标 i。如果写成if (rand() % (i1) 0)那就把所有数组元素都当作流非 target 也会参与替换结果错误。细节三result 的初始值。可以初始化为 -1因为题目保证 target 至少出现一次所以循环内必会更新如果 target 不存在返回 -1 也算一种可预期的行为但 LeetCode 不会出现这种情况。如果遇到“数组为空”的极端输入需要先判空避免整数溢出或越界。另外还有一个很隐蔽的细节如果 nums 是成员变量在 pick 里遍历它时要注意 nums 是否可能在多线程环境下被修改。LeetCode 单线程没问题但工程中可能要考虑加锁或使用不可变快照。这些属于扩展讨论放在后面工程部分细说。4. 两种方案的正面交锋怎么选才不亏4.1 时间空间对照表把两种方案放在一起看优劣就非常清晰了。整理一张对照表方便面试和复习时一眼看出差异。维度哈希表缓存蓄水池抽样预处理时间O(n)无构造时只保存引用pick 时间复杂度O(1)O(n)空间复杂度O(n)O(1)不含原始数组支持流式数据否是支持动态数组不方便自然支持随机均匀性容易实现数学上严格等概率代码复杂度低中适合场景多次查询、数据量可控数据量大、内存受限这里强调一点哈希表方案的 pick O(1) 是理论上限实际还要考虑unordered_map的哈希计算和 vector 的访存蓄水池方案的 pick O(n) 是最坏情况如果 target 出现得很早它还是会傻傻地扫完整个数组因为它“不知道”后面还有没有 target必须全部看完才敢返回。这在某些场景下会觉得浪费但这就是流式算法的代价。4.2 面试官视角哪种方案更高级在面试时如果你只给出哈希表方案面试官一般会追问“能不能不用额外空间”。这就提示你要往蓄水池想。事实上398 在 LeetCode 的标签里明确有 Reservoir Sampling所以面试官如果考这题八成是想听蓄水池抽样的推导而不是哈希表。不过就算你面试时先讲哈希表也完全没问题因为从工程角度哈希表方案在“多次查询”的场景下效率更高是合理的权衡。关键在于你能不能主动分析两种方案的 trade-off而不是只会背代码。一个加分的回答思路是先确认数据规模。如果数组长度在百万级以内且 pick 会被频繁调用哈希表是更好的选择如果数组长度上亿或者数据来自 Kafka、日志文件等流式源就必须用蓄水池。可以这样回答“我会先看约束条件如果内存紧张或者数据流式到达蓄水池抽样 O(1) 空间是唯一可行解如果内存充足并且查询次数多哈希表用空间换时间更合理。”这种回答展示了你在做 engineering trade-off。4.3 变体题目与举一反三理解了蓄水池抽样后LeetCode 上很多随机抽样的题都是纸老虎。最经典的变体是 LeetCode 528 按权重随机选择给定每个下标的权重要求按权重概率随机返回下标。这题可以用前缀和加二分查找本质上和蓄水池抽样思路不同但目的都是控制随机概率。另一个变体是“从数据流中随机选取 k 个元素”这就是标准的蓄水池抽样 k1 版本很多公司的高频题。还可以抽象出“等概率随机整数生成”问题比如用 rand7() 生成 rand10()这也和随机均匀性相关。遇到这类题目我建议你总结一个套路第一步明确随机事件是什么第二步确认是否需要知道总数第三步选择遍历方式第四步用概率公式验证均匀性。把 398 彻底弄懂再去做 382链表随机节点就非常顺因为 382 就是蓄水池抽样在链表上的直接应用。这些题放在一起刷效率会高很多也符合 LeetCode 热门 100 题里“一类题一起刷”的备考思路。5. 实测与常见错误排查别被随机数骗了5.1 用频率检验随机均匀性写完解法后怎么验证它真的“等概率”光看一遍逻辑是不够的。我通常会在本地写一个测试创建一个大小为 100 的数组某个 target 出现 10 次然后调用 pick 十万次统计每个下标出现的次数。理想情况下每个下标出现约一万次。如果某个下标明显偏多或偏少说明随机算法有问题。当然随机数有波动十万次采样下偏差在几个百分点内都算正常别因为一次测试没精确等于一万就慌。更科学的验证方法是计算卡方统计量。把每个下标出现的次数记为 O_i期望次数 E 总次数/k计算sum((O_i - E)^2 / E)得到一个卡方值再查自由度为 k-1 的卡方分布临界值。如果卡方值落在可接受范围说明均匀性没有显著问题。这个方法在工程上做 A/B 测试流量切分时也常用。不过 LeetCode 刷题阶段不需要这么严格用直方图目测就够。5.2 五个容易踩的坑我在反复提交 398 的过程中总结出五个高频坑。第一个坑是把 count 定义成类的成员变量并在多个 pick 之间复用。这样第二次 pick 时 count 已经等于上一次的 target 总数导致概率计算错误。正确做法是 count 和 result 都在 pick 函数内部定义。第二个坑是用 i1 代替 count也就是对数组所有元素计数而不是只对 target 计数。虽然 i1 在数字上一直在增长但非 target 的下标会搅乱随机替换逻辑最终概率完全不对。第三个坑是使用rand() % count时如果 count 是 0target 没出现会触发除零错误。虽然题目保证 target 存在但防御性编程还是要先判空。第四个坑是误以为哈希表方案更快就只采用哈希表结果面试官问“数组是一个流不能预先加载”当场卡壳。第五个坑是本地调试时忘了 srand每次都从同一个种子开始随机导致看起来有规律误以为算法有问题。这个坑很冤枉因为 LeetCode 评测环境会把随机种子设置好而本地不会。5.3 我推荐的调试顺序我这里分享一个实测有效的调试顺序。第一步先用最简单的用例走一遍代码比如nums [1],pick(1)确认返回 0。第二步用重复值用例比如nums [1,1,1],pick(1)手动模拟 count 从 1 到 3每步替换概率分别是 1/1、1/2、1/3确认逻辑没有笔误。第三步写一个循环调用 pick 10000 次打印频率分布观察是否大致均匀。第四步把 nums 换成包含多个不同值的数组随机挑选 target 测试确保不会崩溃。第五步再检查代码中是否有未使用的成员变量、是否用了 C 的随机库但忘了初始化。一开始我建议先用哈希表方案提交保证题通过然后再改成蓄水池方案对比两个提交的耗时和内存。这样既熟悉了两条路又不会被编译细节卡住。等你把两种写法都 run 熟面试时无论从哪个角度问都能接住。6. 跳出题目随机索引的工程应用6.1 从代码到服务发现398 的蓄水池抽样思维在真实系统里到处都是。拿服务发现举例一个服务有 N 个可用实例客户端想把请求均匀地分散到每个实例最简单的方法是把实例列表装进数组随机选一个下标。但如果实例列表是一个动态变化的流每秒钟都有实例注册和下线你不可能每次请求都重新构造一个完整列表。这时可以在流量进入时遍历当前可用实例用蓄水池抽样的方式等概率选一个且只需 O(1) 额外空间。这就是微服务客户端负载均衡里一个很常见的随机策略。再比如日志抽样。一个高吞吐系统每秒产生百万条日志不可能全量落盘。如果只抽 1% 的日志做监控可以维护一个 1/100 的计数器每 100 条日志采一条。但这属于确定性抽样不是等概率随机。如果用蓄水池抽样可以保持从开始到现在每一条日志被采样概率一致并且在不知道总条数的流式环境下也成立。这类算法在监控和可观测性系统里很重要。6.2 并发场景下的随机线程安全在工程中还有一个容易忽略的问题多线程同时调用 pick 时rand() 和 uniform_int_distribution 的线程安全性。标准库的 rand() 使用全局状态多线程调用时会有数据竞争结果可能不是均匀的甚至可能崩溃。C11 的random中如果多个线程共享同一个随机数引擎也需要加锁保护更好的做法是每个线程一个 thread_local 局部随机数引擎避免锁竞争。对于蓄水池抽样 pick即使随机数生成是线程安全的遍历 nums 时如果别处同时修改 nums也会读到不一致数据。所以要么设计成不可变对象要么在遍历时加读锁。刷题时不需要考虑这些但你要知道这题背后的算法一旦落地需要考虑并发和线程模型这也是高级工程师和初级工程师的区别。6.3 一点个人经验最后分享一点我自己的刷题经验。398 这题我前后写过四遍第一遍用哈希表第二遍用蓄水池第三遍尝试用 Python第四遍专门为了面试手推概率公式。每次重写都会发现新的细节比如 rand() 的 modulo bias、count 是 int 还是 size_t、要不要加 random_device。其实 LeetCode 上很多题都是这样第一次 AC 只是开始能清楚解释“为什么这样写”才算真正会了。建议你把 398 和 382、528 这三道题放在一起二刷做一次横向对比你会形成“随机抽样”这一类题的完整方法论以后再遇到类似题目基本就是默写。