26九/1111
单次遍历，带权随机选取问题（二）
还是同样的问题：有一组数量未知的数据，每个元素有非负权重。要求只遍历一次，随机选取其中的一个元素，任何一个元素被选到的概率与其权重成正比。
在前一篇文章中介绍了概率分布的理论值，并用比较简洁高效的函数实现了选取一个元素的方法。现在来看一个神奇的算法，以及相关的证明和实现。
21九/110
单次遍历，带权随机选取问题（一）
在单次遍历，等概率随机选取问题中已经剧透了今天的内容，那就是带权随机选取（Weighted Random Sample）问题。
问题描述：有一组数量未知的数据，每个元素有非负权重。要求只遍历一次，随机选取其中的一个元素，任何一个元素被选到的概率与其权重成正比。
6九/115
单次遍历，等概率随机选取问题
又是一道概率问题，不过跟之前的题目一样，这也是一道非常简单的题目。
问题描述：假设我们有一堆数据（可能在一个链表里，也可能在文件里），数量未知。要求只遍历一次这些数据，随机选取其中的一个元素，任何一个元素被选到的概率相等。O(n)时间，O(1)辅助空间（n是数据总数，但事先不知道）。