您将如何在链表中选择长度未知的统一随机元素? [英] How would you pick a uniform random element in linked list with unknown length?

问题描述

你将如何在一次或两次遍历中选择链表中长度未知的统一随机元素?

How would you pick a uniform random element in linked list with unknown length in one pass or if not two passes?

推荐答案

使用水库采样 http://en.wikipedia.org/wiki/Reservoir_sampling.您只需要一次传递数据.

Use reservoir sampling http://en.wikipedia.org/wiki/Reservoir_sampling . You need only one pass of the data.

选择一个元素:

1. 选择第一个元素(概率 1)
2. 稍后，对于第 k 个元素，以 1/k 的概率选择它(即用第 k 个元素替换现有选择)

我会让你证明这会导致元素的统一选择.

I will let you prove that this results in uniform selection of elements.

这篇关于您将如何在链表中选择长度未知的统一随机元素?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！