牟长青 做网站推广的四个基本要点,哈尔滨公共资源交易网建设工程,做团队网站源码有哪些,微网站开发手机模拟器问题描述
在长度为N的数组中#xff0c;随机等概率选取K个元素#xff0c;如何实现这个随机算法。 思路很简单#xff0c;生成一个[0, N]的随机数index#xff0c;然后返回index上的数值即可。
但是#xff0c;如果输入是一个长度未知的数组比如stream#xff0c;先遍历…问题描述
在长度为N的数组中随机等概率选取K个元素如何实现这个随机算法。 思路很简单生成一个[0, N]的随机数index然后返回index上的数值即可。
但是如果输入是一个长度未知的数组比如stream先遍历得到数组大小在遍历进行K次采样显然不够高效这就引出了蓄水池算法。 蓄水池采样算法可以在一次遍历中得到K次采样结果并且保证等概率N个样本 K次采样每一个元素被pick的概率是 k/N 实现方式为如下步骤
构建一个长度为K的数组(蓄水池)保存采样结果将数组[0, k]数值赋值给蓄水池数组遍历剩下[k1, N]每一次迭代中产生一个 的index, 如果index K那么将原来处在该index的结果覆盖掉。以此类推最后返回蓄水池数组结果
代码如下
Leetcode 398. random pick index
class Solution {int[] reservior;Random rand new Random();int[] copy;public Solution(int[] nums) {// 本题目只需要选取一个样本 k 1copy nums;reservior new int[1];reservior[0] -1;}public int pick(int target) {int cnt 0;for (int i0; icopy.length; i) {if (copy[i]target) {cnt;int randNum rand.nextInt(cnt);if (randNum0) {reservior[0] i;}}}return reservior[0];}
}
时间复杂度空间复杂度。
数学原理
上述步骤中最难理解无非就是第三步为什么这样做就可以实现每一个元素被选的概率是k/N。
对于 的元素 在 k 步之前他们被选中是没有随机性的 p 100% 在 k1 步时被第k1个元素替代的概率 (k1)元素被选中的概率 * i 这个index被选中的概率根据上面实现第 i 个index被选中概率为 1/k (Java中random.nextInt是左闭右开)而 k1个元素被选中的概率为 k/k1(random生成的随机数小于k都为选中) 被第k1个元素替代的概率 那么反过来第i个元素被保留的概率为 那么在 N 步第 i 个元素被保留的概率应该为 k1步被保留的概率 * k2步被保留的概率 * ... * N步被保留的概率也就是 对于 的元素在k步之前是没有概率的因为不存在 在 k1步第k1个元素被选中的概率为 由于第 k1的元素原本不存在没有先置概率。在 k2步第k1个元素被保留的概率 第k1步被选中概率 * 第k2步没有选中第k2个元素的概率 第k1个元素被保留的概率 在 N 步第k1个元素被保留的概率 有几点细节需要留意
所有的数值只有一次选中的机会就是数组遍历到那个index的时候如果没有被选中那么以后再也没有机会被重新选中。只有当时被选中才有保留的机会 [0, k]的元素第一次被选中概率为 100%[k1, N]的元素第一次被选中概率为 不管数组中那个元素只要被选中保留到最后作为返回值的概率都是
