LeetCode刷题笔记——ReserviorSampling

在面试中遇到了这么一道问题：有一个抽奖系统，内存很小（存不下所有用户的id），在截止时间前任何用户都可以访问该系统参与一次抽奖，到了截止时间后要求以等概率的可能性选取一个合法用户作为幸运用户。比如截止时间前有十个用户访问该系统，那么要求每个用户都有 10% 的概率被选中，如果截止时间前有100个用户访问该系统，那么到了截止时间的时候，要求每个用户有 1% 的概率被选中。

由于之前看过《编程珠玑》，所以很快的想到了该问题实际上是蓄水池抽样问题加了一个实际场景。蓄水池问题解决的就是在流数据中进行等概率抽样的问题。先考虑一个简单情况，需要在流数据中等概率的选取一个元素。那么算法思想是，对于第$$$k$$$个元素，有$$$\frac{1}{k}$$$的概率被选中，作为当前的“幸运元素”，当流算法需要抽样时返回当前元素即可。

使用数学归纳法证明，只有一个元素时显然成立。假设当前是第$$$k+1$$$个元素，前面每一个元素都各自有$$$\frac{1}{k}$$$的概率被选中，那么在本次，有$$$\frac{1}{k+1}$$$的概率选中当前元素，对于之前的每个元素，有$$$\frac{k}{k+1}×\frac{1}{k}=\frac{1}{k+1}$$$的概率被选中。

扩展为等概率的抽样n个元素的话。算法主要思想为：如果当前蓄水池不足$$$k$$$个，直接加入蓄水池。否则，对于第$$$k$$$个元素以概率$$$\frac{n}{k+1}$$$选择是否让当前元素被选中。若被选中，则从蓄水池中随机选择一个元素并用当前元素替换它。

同样用数学归纳法证明，认为数据流至少有n个元素，对于前n个元素，显然成立。假设已经处理过k个元素，前面的每个元素有$$$\frac{1}{k}$$$，可以发现该轮操作后留下的元素的概率是$$$\frac{1}{k+1}$$$。

leetcode中有两个关于该算法的习题。

382. Linked List Random Node

398. Random Pick Index