2022-1-16 LeetCode 每日一题 No.382 链表随机节点 题解

原贴地址：https://dawnmagnet.github.io/algorithm-station/docs/2022/1/16

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

实现 Solution 类：

• Solution(ListNode head) 使用整数数组初始化对象。

• int getRandom() 从链表中随机选择一个节点并返回该节点的值。链表中所有节点被选中的概率相等。

示例：

输入["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"][[[1, 2, 3]], [], [], [], [], []]输出[null, 1, 3, 2, 2, 3]
解释Solution solution = new Solution([1, 2, 3]);solution.getRandom(); // 返回 1solution.getRandom(); // 返回 3solution.getRandom(); // 返回 2solution.getRandom(); // 返回 2solution.getRandom(); // 返回 3// getRandom() 方法应随机返回 1、2、3中的一个，每个元素被返回的概率相等。

提示：

• 链表中的节点数在范围 [1, 10^4104] 内

• -10^4−104 <= Node.val <= 10^4104

• 至多调用 getRandom 方法 10^4104 次

进阶：

• 如果链表非常大且长度未知，该怎么处理？

• 你能否在不使用额外空间的情况下解决此问题？

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/linked-list-random-node 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路分析

这种题目一般都是表面简单，做出来也很简单，但要是完成题目中所有要求的进阶任务还是很有挑战性的。

在本题中，我们手里与其说有一个链表，倒不如说有一个未知长度的数据流。实际上本题真正想要挑战我们的是如何在一个未知长度的数据流中去取随机数（根据进阶中的要求可以知道），还要求不能使用常数空间，如果这个数据流很长但算法需要的比常数空间大（如 O(n)），那将会是一个非常可怕的算法。

那么本题就要隆重介绍一个算法，叫做蓄水池抽样。不懂也很正常，这种东西就是一回生二回熟，多看看就知道了。

记住一件事，蓄水池抽样这个算法就是用来做在未知长度的数据流中获取随机数的

假设我们已经处理了 n 个数字，获得了前 nn 个数字中的一个随机数结果，那么这个结果对于前 nn 个数的概率一定是相同的，也就是每个数字有\frac1nn1​的概率取到。在这种背景下，如果我们加入一个新的数字，也就是第 n+1 个数字，这种时候我们肯定希望，所有数字被取到的概率都是$\frac{1}{n+1}$​，当然也包含这个新加进来的数字。

那么如何完成这个概率转变的过程呢？答案就是确保第 n+1 个数字被取到的概率是$\frac{1}{n+1}$。因为在确保了这个事情之后，因为取到前 n 个数字的概率是均等的，如果在新加入的第 n+1 个数字保持$\frac{1}{n+1}$概率，那么我们可以保证前 n 个数字也是这个概率。

以上是一个对蓄水池抽样算法的简单说明和证明。有兴趣的同学可以在网上自行查阅更多资料。

讲完了这么一些个步骤，算法干的什么事也就很明了了。对于第 n 个数字，我们首先取一个随机数，如果概率小于$\frac{1}{n}$，我们就将结果改为第 n 个数字，否则就不动，（数据流）继续往下走。

在 LeetCode 平台上，Rust 支持第三方的随机数库，名字叫做 rand，具体的文档可以在https://docs.rs/rand/latest/rand/进行查询。

Rust 代码

use rand::prelude::*;struct Solution {    node: Option<Box<ListNode>>}impl Solution {    fn new(head: Option<Box<ListNode>>) -> Self {        Solution { node: head }    }    fn get_random(&self) -> i32 {        let mut node = self.node.clone();        let mut res = 0;        let mut factor = 1;        let mut rng = rand::thread_rng();        while let Some(node_some) = node {            let rnd: i32 = rng.gen();            if rnd % factor == 0 {                res = node_some.val;            }            factor += 1;            node = node_some.next;        }        res    }}