问题描述

能否从一个未知大小的集合中随机抽取个元素，使得个元素的被选中的概率相等，要求只能遍历一次集合？

结论

设集合大小为，只要在遍历过程中，令第个元素被选中的概率为，就可以使得最终每个元素被选中的概率为。

证明

使用归纳法证明

1. 归纳基础：当时，显然即所有元素都被选中，每个元素被选中的概率为 1。
2. 归纳假设：假设当时，结论也成立。
3. 归纳推理：则当时，根据结论有第个元素被选中的概率为，此时对于前面个元素中的某一个元素（第个，）仍然被选中的概率为：，结论也成立。（表示第个元素被选中且恰好替换了第个元素的概率）。
4. 由（1）（2）（3）可知，结论成立。

应用场景

当集合很大且大小未知，不适合一次性加载到内存中时。

练习题目

题目来源：[LeetCode]382. 链表随机节点
解析：根据进阶要求，题目可以简化为从一个很大的集合中，等概率随机返回其中一个元素，对应的水塘抽样。