蓄水池抽样算法（Reservoir Sampling）
**蓄水池抽样算法（Reservoir Sampling）**
**问题描述**
蓄水池抽样算法用于解决这样一种场景：当数据流（或链表）的长度N非常大，且无法一次性加载到内存时，如何**等概率**地随机抽取k个元素（k≥1）。该算法保证每个元素被选中的概率均为k/N，且只需遍历数据一次，空间复杂度仅为O(k)。
---
**核心思想与步骤（以k=1为例）**
当只需随机选取1个元素时，算法步骤如下：
1. **初始化**：将结果变量res初始化为第一个元素。
2. **遍历处理*
2025-11-05 16:16:28
0