1.简介

水塘抽样是一系列的随机算法，其目的在于从包含n个项目的集合S中选取k个样本，其中n为一很大或未知的数量，尤其适用于不能把所有n个项目都存放到内存的情况。最常见例子为Jeffrey Vitter在其论文中所提及的算法R。

2.算法步骤：

集合使用s表示，共有n个样本，使用j表示样本次序，池塘使用p表示：

1. 选取s中的前k个样本放入池塘p，此时j∈[0,k-1]；
2. 当j>=k时，在范围[0,j]内随机生成索引r，即r∈[0,j]：
   如果r<k，即r∈[0,k-1]，则使用s[j]替换p[r]，即p[r]=s[j]；

3. 使用案例

3.1 可否在一未知大小的集合中，等概率随机取出K个元素？

    // 水塘抽样算法public ArrayList<Integer> randomSelect(ArrayList<Integer> list,int k){// 1.选取前k个元素ArrayList<Integer> pool=new ArrayList<>(list.subList(0,k));// 2.对于i<=k的元素，进行随机替换Random random=new Random();for (int i=k;i<list.size();i++){int r=random.nextInt(i+1);if (r<k){pool.set(r,list.get(i));}}return pool;}

4.力扣382. 链表随机节点

给你一个单链表，随机选择链表的一个节点，并返回相应的节点值。每个节点 被选中的概率一样 。
实现 Solution 类：

• Solution(ListNode head) 使用整数数组初始化对象。 int getRandom()
• 从链表中随机选择一个节点并返回该节点的值。链表中所有节点被选中的概率相等。

    // 方式一：顺序表+二分查找class Solution {ArrayList<ListNode> nodes=new ArrayList<>();public Solution(ListNode head) {// 统计节点数量ListNode tail=head;while (tail!=null){nodes.add(tail);tail=tail.next;}}public int getRandom() {// 计算随机索引int index=new Random().nextInt(nodes.size());  // [0,bound)// 二分查找选取节点ListNode tar=binarySearch(index);return tar.val;
//            return nodes.get(index);}private ListNode binarySearch(int index) {int l=0,r=nodes.size()-1;while (l<=r){int m=l+(r-l)/2;if (m==index){return nodes.get(m);}else if (m<index){l=m+1;}else if (m>index){r=m-1;}}return null;}}

/* 方式二：水塘抽样算法/
class Solution {ListNode head;Random random=new Random();public Solution(ListNode head) {this.head=head;}public int getRandom() {ListNode tail=head.next;int index=1;  // 记录第几个元素int val=head.val;while (tail!=null){int r=random.nextInt(index+1);if(r==0){val=tail.val;}index++;tail=tail.next;}return val;}
}

参考：
1）https://baike.baidu.com/item/%E6%B0%B4%E5%A1%98%E6%8A%BD%E6%A0%B7/10490257?fr=aladdin
2）https://blog.csdn.net/wq3095435422/article/details/124413184