在链表中查找元素

Question

有一个数据结构为迭代器提供了以下接口：

struct iterator {
    T value();
    void next();
    bool isValid();
}

您将如何设计一种算法，在循环结束时 returns 列表中每个元素的某个值具有相同的概率？列表可以很长，所以列表的长度不能用 int 或 long 表示。无法修改列表。

有什么想法吗？谢谢

Answer 1

你不知道列表的长度，所以你必须一直迭代到最后。您需要保留当前选择的项目值（或项目，但在您的问题中似乎无法做到这一点）的副本。然后对于您迭代到的每个新项目，您需要确定是否应该保留或更改所选项目，概率递减。

由于您声明列表的长度可能不适合 native/primitive 数据类型（我假设您的意思是当您谈论 int 和 long 时，它们是编程语言甚至方言特定的数据类型，并且您没有指定编程语言），我认为您的意思是列表可能任意长。所以你需要一个bignum库，它可以给你任意的随机数。

伪代码：

T current = empty value
bignum index = 0
iterator = first item of list
while iterator.isValid()
    index = index + 1
    if bignum_random_below(index) == 0
        # 0 is interpreted as, take value from current index,
        # everything else is interpreted as keep the previous value
        current  = iterator.value()
    end if
    iterator.next()
end while
# index value 0 indicates empty list, even if T doesn't have empty value

来自 M Oehm 的评论：这叫做 reservoir sampling。

在链表中查找元素

find element in linked list

algorithm

computer-science

linked-list