乐趣区

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

力扣中对于蓄水池抽样问题官网标签是 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. 非重叠矩形中的随机点

总结

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

退出移动版