algorithm - 遍历单向链表随机取一个元素

Question

我有一个单向链表，但不知道它的大小。

我想得到这个列表中的一个随机元素，我只有一次机会遍历这个列表。 (不允许我遍历两次以上)

这个问题的算法是什么？谢谢!

Answer 1

这只是 reservoir sampling具有大小为 1 的水库。

其实很简单

1. 无论如何都选择第一个元素(对于长度为 1 的列表，第一个元素始终是样本)。
2. 对于概率为 1/n 的所有其他元素，其中 n 是到目前为止观察到的元素数，您将已选择的元素替换为您所在的当前元素。

这是均匀采样的，因为在一天结束时选择任何元素的概率是 1/n(读者练习)。