关于算法:不知道蓄水池抽样算法那就进来看看吧

2次阅读

共计 1689 个字符，预计需要花费 5 分钟才能阅读完成。

力扣中对于蓄水池抽样问题官网标签是 2 道，依据我的做题状况来看，可能有三四道。比重算是比拟低的，大家能够依据本人的理论状况选择性把握。

蓄水池抽样的算法思维很奇妙，代码简略且容易了解，就算不把握它，作为理解也是很不错的。

给出一个数据流，咱们须要在此数据流中随机选取 k 个数。因为这个数据流的长度很大，因而须要边遍历边解决，而不能将其一次性全副加载到内存。

请写出一个随机抉择算法，使得数据流中所有数据被 等概率 选中。

这种问题的表达形式有很多。比方让你随机从一个矩形中抽取 k 个点，随机从一个单词列表中抽取 k 个单词等等，要求你等 概率随机抽取。不论形容怎么变，其本质上都是一样的。明天咱们就来看看如何做这种题。

这个算法叫蓄水池抽样算法（reservoid sampling）。

其基本思路是：

构建一个大小为 k 的数组，将数据流的前 k 个元素放入数组中。
对数据流的前 k 个数先不进行任何解决。
从数据流的第 k + 1 个数开始，在 [1, i] 之间选一个数 rand，其中 i 示意以后是第几个数。
如果 rand 大于等于 k 什么都不做
如果 rand 小于 k，将 rand 和 i 替换，也就是说抉择以后的数代替曾经被选中的数（备胎）。
最终返回幸存的备胎即可

这种算法的外围在于先以某一种概率选取数，并在后续过程以另一种概率换掉之前曾经被选中的数。因而实际上每个数被最终选中的概率都是 被选中的概率 * 不被替换的概率。

伪代码：

伪代码参考的某一本算法书，并略有批改。

Init : a reservoir with the size：k
for i= k+1 to N
    if(random(1, i) < k) {SWAP the Mth value and ith value}

这样能够保障被抉择的数是等概率的吗？答案是必定的。

当 i <= k，i 被选中的概率是 1。
到第 k + 1 个数时，第 k + 1 个数被选中的概率（走进下面的 if 分支的概率）是 $\frac{k}{k+1}$，到第 k + 2 个数时，第 k + 2 个数被选中的概率（走进下面的 if 分支的概率）是 $\frac{k}{k+2}$，以此类推。那么第 n 个数被选中的概率就是 $\frac{k}{n}$
下面剖析了被选中的概率，接下来剖析不被替换的概率。到第 k + 1 个数时，前 k 个数被替换的概率是 $\frac{1}{k}$。到前 k + 2 个数时，第 k + 2 个数被替换的概率是 $\frac{1}{k}$，以此类推。也就是说所有的被替换的概率都是 $\frac{1}{k}$。晓得了被替换的概率，那么不被替换的概率其实就是 1 – 被替换的概率。

因而对于前 k 个数，最终被抉择的概率都是 1 * 不被 k + 1 替换的概率 * 不被 k + 2 替换的概率 * … 不被 n 替换的概率，即 1 * (1 – 被 k + 1 替换的概率) * (1 – 被 k + 2 替换的概率) * … (1 – 被 n 替换的概率)，即 $1 \times (1 – \frac{k}{k+1} \times \frac{1}{k}) \times (1 – \frac{k}{k+2} \times \frac{1}{k}) \times … \times (1 – \frac{k}{n} \times \frac{1}{k}) = \frac{k}{n} $。

对于第 i (i > k) 个数，最终被抉择的概率是第 i 步被选中的概率 * 不被第 i + 1 步替换的概率 * … * 不被第 n 步被替换的概率，即 $\frac{k}{k+1} \times (1 – \frac{k}{k+2} \times \frac{1}{k}) \times … \times (1 – \frac{k}{n} \times \frac{1}{k}) = \frac{k}{n} $。

总之，不论是哪个数，被选中的概率都是 $\frac{k}{n}$，满足概率相等的需要。

382. 链表随机节点
398. 随机数索引
497. 非重叠矩形中的随机点

蓄水池抽样算法外围代码非常简单。然而却不容易想到，尤其是之前没见过的状况下。其外围点在于每个数被最终选中的概率都是 被选中的概率 * 不被替换的概率。于是咱们能够采取某一种动静伎俩，使得每一轮都有概率选中和替换一些数字。下面咱们有给出了概率相等的证实过程，大家无妨本人尝试证实一下。之后联合文末的相干题目练习一下，成果会更好。

正文完