随机算法之水塘抽样算法

预计阅读时间：5 分钟我最近在 LeetCode 上做到两道非常有意思的题目，382 和 398 题，关于水塘抽样算法（Reservoir Sampling），本质上是一种随机概率算法，解法应该说会者不难，难者不会。我第一次见到这个算法问题是谷歌的一道算法题：给你一个未知长度的链表，请你设计一个算法，只能遍历一次，随机地返回链表中的一个节点。这里说的随机是均匀随机（uniform random），也就是说，如果有n个元素，每个元素被选中的概率都是1/n，不可以有统计意义上的偏差。一般的想法就是，我先遍历一遍链表，得到链表的总长度n，再生成一个[1,n]之间的随机数为索引，然后找到索引对应的节点，不就是一个随机的节点了吗？但题目说了，只能遍历一次，意味着这种思路不可行。题 ………………………………