algorithm - 你会如何在未知长度的链表中选择一个统一的随机元素？

Question

如果不是两次，您将如何在链表中选择长度未知的统一随机元素？

Answer 1

使用水库采样 http://en.wikipedia.org/wiki/Reservoir_sampling .您只需要传递一次数据。

选择一个元素:

1. 选择第一个元素(概率 1)
2. 稍后，对于第 k 个元素，以 1/k 的概率选择它(即用第 k 个元素替换现有选择)

我会让你证明这会导致元素的统一选择。