蓄水池抽样算法（Reservoir Sampling） 问题描述 蓄水池抽样算法用于解决这样一种场景：当数据流（或链表）的长度N非常大，且无法一次性加载到内存时，如何 等概率 地随机抽取k个元素（k≥1）。该算法保证每个元素被选中的概率均为k/N，且只需遍历数据一次，空间复杂度仅为O(k)。 核心思想与步骤（以k=1为例） 当只需随机选取1个元素时，算法步骤如下： 初始化 ：将结果变量res初始化为第一个元素。 遍历处理 ：对于第i个元素（i从1开始计数）： 以概率 1/i 决定是否用当前元素替换res。 具体操作：生成一个 [ 0,1)范围内的随机数r，若r < 1/i，则更新res为当前元素。 终止 ：遍历结束后，res即为随机选取的结果。 为什么概率是1/N？ 第1个元素：被选中的概率 = 1（初始化选中） × [ 未被第2个元素替换的概率] × ... × [ 未被第N个元素替换的概率 ] = 1 × (1 - 1/2) × (1 - 1/3) × ... × (1 - 1/N) = 1 × (1/2) × (2/3) × ... × ((N-1)/N) = 1/N。 第i个元素：被选中的概率 = 1/i（在第i步被选中） × [ 未被后续元素替换的概率 ] = 1/i × (1 - 1/(i+1)) × ... × (1 - 1/N) = 1/i × (i/(i+1)) × ... × ((N-1)/N) = 1/N。 推广到k≥1的情况 当需要抽取k个元素时，算法步骤如下： 初始化 ：将前k个元素直接放入蓄水池（结果数组res）。 遍历处理 ：对于第i个元素（i从k+1开始）： 以概率 k/i 决定是否将当前元素加入蓄水池。 若决定加入，则从蓄水池中 随机替换掉一个元素 （等概率选择1到k的下标）。 终止 ：遍历结束后，蓄水池中的k个元素即为随机抽样结果。 为什么每个元素被选中的概率是k/N？ 对于前k个元素： 初始时肯定被选中。第i个元素（i>k）加入时，某个特定初始元素被替换的概率 = (k/i) × (1/k) = 1/i。 因此该初始元素最终保留的概率 = ∏(i=k+1 to N) (1 - 1/i) = k/N。 对于第i个元素（i>k）： 被选中的概率 = k/i（在第i步被选中） × ∏(j=i+1 to N) [ 1 - (k/j) × (1/k) ]（未被后续替换） = k/i × ∏(j=i+1 to N) (1 - 1/j) = k/i × (i/N) = k/N。 示例演示（k=2, 数据流[ a,b,c,d]） 初始化：res = [ a, b ]（i=2）。 处理c（i=3）：以概率2/3决定是否加入。若加入，随机替换res中的一个位置。 处理d（i=4）：以概率2/4决定是否加入。若加入，随机替换res中的一个位置。 最终res中的两个元素各自被选中的概率均为2/4=1/2。 关键应用场景 大数据流中的随机抽样（如日志抽样、推荐系统候选集生成）。 无法预知总长度的链表随机节点选取（如随机播放歌曲列表）。 通过这种巧妙的概率设计，蓄水池抽样算法用极小空间实现了海量数据流的公平随机抽样。