获取单向链表的随机元素通过一次遍历 [英] Get a random element in single direction linked list by one time traverse

问题描述

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

I have a single direction linked list without knowing its size.

我想在这个列表中随机元素，而我只是有一次有机会遍历列表。 （我不是允许通过两次或更多次）

I want to get a random element in this list, and I just have one time chance to traverse the list. (I am not allowed to traverse twice or more)

什么是算法对于这个问题？谢谢！

What’s the algorithm for this problem? Thanks!

推荐答案

这是刚刚水库取样与水库尺寸1。

This is just reservoir sampling with a reservoir of size 1.

本质上，它是非常简单的。

Essentially it is really simple

1. 接的第一个元素，无论（对于长度为1的列表，第一元件总是样品）。
2. 有关的概率是1每隔一个元件/ n，其中n是观察到目前为止，则与当前元素你在更换已经拾取元件元素数。

此被均匀地采样，因为在一天结束时采摘的任何元素的概率为1 / N（锻炼到读取器）。

This is uniformly sampled, since the probability of picking any element at the end of the day is 1/n (exercise to the reader).

这篇关于获取单向链表的随机元素通过一次遍历的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！