algorithm - 设计一种算法从链表中随机选择一个元素

Question

可能重复：
如何在链表中选择一个长度未知的统一随机元素？

假设我们想从链表中随机选择一个元素，但我们不知道链表的长度。

设计一种算法，它需要尽可能少的运行时间来随机选择元素。

Answer 1

有一个简单的算法O(N)，获取长度，然后选择一个元素。

但是你可以做得更好，使用在线算法，只访问每个元素一次：

您选择第一个元素作为答案，然后在第kth 个元素上用概率为 的元素替换您的答案1/k。这种方法没有偏差的事实可以用数学归纳法来证明。

广义版本（选择 k 个元素）是水库采样。

Answer 2

考虑一下：我假设您有一个变量来跟踪您的链接列表中有多少项目（标准编程实践）。如果你有一个传入该变量的函数，你所要做的就是有一个指向链表中一个项目的指针，并将指针设置为 rand() % Amount_Of_Items 然后让函数返回指针，如果你必须使用它。