蓄水池抽样算法形式一

视频链接

B站视频链接

使用场景

给定一个数据流，数据流长度N很大，且N直到处理完所有数据之前都不可知，请问如何在只遍历一遍数据（O(N)）的情况下，能够随机选取出m个不重复的数据

伪代码

保证了每个字符串的取值概率都是等概率的；
image.png

  1. public String core(String[] lines) {
  3.     int i = 0;
  4.     String res = null;
  5.     for(String line : lines) {
  6.         i++;
  7.         r = random.nextDouble();
  8.         if(r < 1/((double)i)) {
  9.             res = line;
  10.         }
  11.     }
  13.     return res;
  14. }

形式二

题目链接

力扣 - 随机数索引
image.png

实现代码

  1. class Solution {
  2.     int[] nums;
  3.     Random random;
  5.     public Solution(int[] nums) {
  6.         this.nums = nums;
  7.         random = new Random();
  8.     }
  10.     public int pick(int target) {
  11.         int ans = 0;
  12.         for (int i = 0, cnt = 0; i < nums.length; ++i) {
  13.             if (nums[i] == target) {
  14.                 ++cnt; // 第 cnt 次遇到 target
  15.                 if (random.nextInt(cnt) == 0) {
  16.                     ans = i;
  17.                 }
  18.             }
  19.         }
  20.         return ans;
  21.     }
  22. }