## 水库抽样算法 **问题描述：** **输入输出描述：** （鼓励以可视化的方式展示算法效果） ### 返回一个 ### 返回 $k$ 个（水库容量为 $k$ ）

水库抽样（Reservoir Sampling）是一种在线随机采样的算法，特别适合处理数据流场景，比如从大规模日志文件或实时网络数据中抽取部分样本进行分析。它的基本思想是在数据流不断到来的过程中，保持一个小容量的“水库”（通常是固定大小的$k$），按照一定的概率选择新的元素替换旧的元素，使得每次新元素到达时，它被选中的概率都是相等的。

**算法步骤如下：**
1. 初始化一个大小为$k$的数组`reservoir`，将前$k$个元素当作初始样本。
2. 对于每个后续到来的数据元素（索引为$i$），从0到当前元素（包括i）进行均匀随机选取一个整数$r$。
3. 如果$r$小于$k$，则更新`reservoir[r]`为当前元素。
4. 数据流继续时，仅`reservoir[0]`至`reservoir[k-1]`内的元素可能会改变。

**示例输出：**
假设数据流中有100个元素，我们想要抽取10个样本（$k=10$）。每经过一个元素，我们就有一个10%的机会将这个元素加入样本中。

**返回结果：**
当遍历完所有数据后，`reservoir`数组就会包含$k$个随机选取的样本。

**视觉化展示：**
可以用图形表示数据流如何随时间流动，其中x轴代表数据流位置，y轴代表样本位置。每行代表一个数据点，如果该点被选入，则对应的位置会有一个标记，最终显示的将是10个有标记的样本。