一次遍历获取单向链表中的随机元素

Question

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

我想在这个列表中获取一个随机元素，并且我只有一次机会遍历该列表。 （不允许遍历两次及以上）

这道题的算法是什么？谢谢！

Answer 1

这只是对大小为 1 的水库进行的水库采样。

本质上它非常简单，

1. 无论如何都选择第一个元素（对于列表长度为 1，第一个元素始终是样本）。
2. 对于概率为 1/n 的每个其他元素，其中 n 是迄今为止观察到的元素数量，您可以将已选取的元素替换为当前所在的元素。

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

Answer 2

这可能是一个面试问题。数据科学家使用油藏采样将大量数据中的相关数据存储在有限的存储空间中。

如果您必须从任何具有元素 n 的数组中收集 k 个元素，以便收集到的每个元素的概率应该相同 (k/n)，请执行以下两个步骤：

1) 将前 k 个元素存储在存储中。
2）当下一个元素（k+1）来自流时，显然你的集合中已经没有空间了。生成一个从o到n的随机数，如果生成的随机数小于k假设l，则替换storage[l ] 与流中的 (k+1) 个元素。

现在，回到你的问题，这里存储大小是 1。所以你将选择第一个节点，迭代列表中的第二个元素。现在生成随机数，如果它是 1，则保留样本，否则将存储元素从列表

Answer 3

这个问题可以通过水库采样来完成。它基于从 n 个项目中选择 k 个随机项目，但这里 n 可以非常大（不必适合内存！）并且（如您的情况）最初未知。

维基百科有一个可以理解的算法，我在下面引用：

array R[k];    // result
integer i, j;

// fill the reservoir array
for each i in 1 to k do
    R[i] := S[i]
done;

// replace elements with gradually decreasing probability
for each i in k+1 to length(S) do
    j := random(1, i);   // important: inclusive range
    if j <= k then
        R[j] := S[i]
    fi
done

这个问题只需要 1 个值，所以我们取 k=1。

C 实现：

https://ideone.com/txnsas

Answer 4

这是我发现的最简单的方法，它工作正常并且易于理解：

public int findrandom(Node start) {
    Node curr = start;
    int count = 1, result = 0, probability;
    Random rand = new Random();

    while (curr != null) {
        probability = rand.nextInt(count) + 1;
        if (count == probability)
            result = curr.data;
        count++;
        curr = curr.next;
    }
    return result;
}