382. 链表随机节点

简单看下暴力做法，使用一个数组存储所有的链表数据：

  1. class Solution {
  2.     List<Integer> list = new ArrayList<>();
  3.     Random random = new Random(20220116);
  4.     public Solution(ListNode head) {
  5.         while (head != null) {
  6.             list.add(head.val);
  7.             head = head.next;
  8.         }
  9.     }
  10.     public int getRandom() {
  11.         int idx = random.nextInt(list.size());
  12.         return list.get(idx);
  13.     }
  14. }

蓄水池抽样的思路（学习三叶姐）：
这算法的核心是对无限的数据流进行抽样，具体的做法为，从所有样本中抽取若干个，要求每个样本被抽到的概率相等。
具体做法为：从前往后处理每个样本，每个样本成为答案的概率为 蓄水池抽样 - 图1（注意，考虑的是一个无限的流），其中 **i** 为样本编号（编号从 1 开始），最终可以确保每个样本成为答案的概率均为 蓄水池抽样 - 图2（其中 **n** 为样本总数）。
image.png
看代码：

  1. struct Solution {
  2.     head: Option<Box<ListNode>>
  3. }
  6. /**
  7.  * `&self` means the method takes an immutable reference.
  8.  * If you need a mutable reference, change it to `&mut self` instead.
  9.  */
  10. impl Solution {
  12.     fn new(head: Option<Box<ListNode>>) -> Self {
  13.         Self{
  14.             head
  15.         }
  16.     }
  18.     fn get_random(&self) -> i32 {
  19.         use rand::prelude::*;
  20.         let (mut res, mut idx, mut head) = (-1, 1, &self.head);
  21.         while let Some(node) = head {
  22.             // 从第一个节点开始筛选，扔一个随机数，如果为0的时候
  23.             // 意味着甩到的概率为1/idx，也就意味着我们选目前的这个元素
  24.             // 其概率为1/idx，在延到无穷流中，也能够满足1/n的概率
  25.             if thread_rng().gen_range(0, idx) == 0 { res = node.val; }
  26.             idx+=1;
  27.             head = &node.next;
  28.         }
  30.         res
  31.     }
  32. }