在未知个数的链表中均匀随机选一个元素返回。


例如:
list: node1 -> node2 -> node3 -> node4 -> node5 -> node6 -> NULL

这个链表有6元素,每个node可能被选到的概率为1/6。

但一般情况下,node的个数是未知的(没有链表头没有记录个数的状态变量)。

写一个函数,如何在这种情况下,能均匀的概率选取出链表其中一个node。
已邀请:

cpcs - 诚实努力

赞同来自: flyfatasy 画儿 SuiterChik EpisodeXI bropaper


遍历链表 对第i个节点 (i从1开始),均匀产生随机数 x
若x % i == 0 则暂时保留这个节点 (换掉之前保留的节点)

(1) 如果只有1个节点 选择第1个节点的概率是1
(2) 如果只有2个节点 第一步先选择第1个节点 然后再以1/2的概率换掉, 所以每个节点选择的概率是1/2
(3) 假设遍历到链表第n个节点的时候 选择目前保留的n个节点的概率都是1/n
则对第(n + 1)个节点, 我们有1/(n + 1)的概率选择它,有n / (n + 1)的概率保留原来保存的节点,所以保留前n个节点中每个的概率是(这是个条件概率) 1/n * (n / (n + 1)) = 1 / (n + 1) ,可见最终保留每个节点的概率都是1/(n + 1)

这种抽样方法叫水库抽样,可以扩展到要保留k个的情况。

要回复问题请先登录注册

返回顶部