algorithm - 从具有均匀分布概率的流中选择一个元素

Question

给你:

1. 一个流(流的结尾是EOF)
2. 函数 next()获取流中的下一个元素并推进流中的指针
3. 随机生成器生成介于 0 和 1(含)之间的 float

输出:

• 被证明是随机(均匀分布)选择的元素

您可以使用一个或两个变量。

你不能使用数组/列表，你不能告诉trying to get all elements out and store them all and then pick的方式.

---

这是一道面试题。

我的想法是:

1. 我使用变量 cur存储最近保留的元素
2. 所以，如果我得到一个新元素，我会使用生成器生成一个随机的 0 或 1，如果它是 0，那么 cur = new element ;否则，继续；
3. 如果我得到 EOF，则返回 cur

---

我的想法对吗？如何证明？

---

同样的问题

How would you pick a uniform random element in linked list with unknown length?

Answer 1

设当前元素的索引为i。

选择“记住”当前元素的概率为 1/i。当到达 EOF 时，生成你记得的元素。

最后，对于索引为 i 的每个元素，都有一个被选中的概率:

可以按照这些准则使用归纳法进行正式证明。