题目描述
这是 LeetCode 上的 382. 链表随机节点 ，难度为 中等。
Tag :「链表」、「模拟」、「蓄水池抽样」
给你一个单链表，随机选择链表的一个节点，并返回相应的节点值。每个节点 被选中的概率一样 。
实现 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(); // 返回 1 solution.getRandom(); // 返回 3 solution.getRandom(); // 返回 2 solution.getRandom(); // 返回 2 solution.getRandom(); // 返回 3 // getRandom() 方法应随机返回 1、2、3中的一个，每个元素被返回的概率相等。 复制代码
提示：
- 链表中的节点数在范围 [1, 10^4] 内链表中的节点数在范围[1,104]内
- -10^4 <= Node.val <= 10^4−104<=Node.val<=104
- 至多调用
getRandom方法 10^4104 次
进阶：
- 如果链表非常大且长度未知，该怎么处理？
- 你能否在不使用额外空间的情况下解决此问题？
模拟
由于链表长度只有 10^4104，因此可以在初始化时遍历整条链表，将所有的链表值预处理到一个数组内。
在查询时随机一个下标，并将数组中对应下标内容返回出去。
代码（感谢 @Benhao 同学提供的其他语言版本）：
class Solution { List<Integer> list = new ArrayList<>(); Random random = new Random(20220116); public Solution(ListNode head) { while (head != null) { list.add(head.val); head = head.next; } } public int getRandom() { int idx = random.nextInt(list.size()); return list.get(idx); } } 复制代码
class Solution: def __init__(self, head: Optional[ListNode]): self.nodes = [] while head: self.nodes.append(head) head = head.next def getRandom(self) -> int: return self.nodes[randint(0, len(self.nodes) - 1)].val 复制代码
type Solution struct { Nodes []int } func Constructor(head *ListNode) Solution { nodes := make([]int, 0) for head != nil { nodes = append(nodes, head.Val) head = head.Next } return Solution{nodes} } func (this *Solution) GetRandom() int { return this.Nodes[rand.Intn(len(this.Nodes))] } 复制代码
- 时间复杂度：令 nn 为链表长度，预处理数组的复杂度为 O(n)O(n)；随机获取某个值的复杂度为 O(1)O(1)
- 空间复杂度：O(n)O(n)
蓄水池抽样
整理题意：总的样本数量未知，从所有样本中抽取若干个，要求每个样本被抽到的概率相等。
具体做法为：从前往后处理每个样本，每个样本成为答案的概率为 \frac{1}{i}i1，其中 ii 为样本编号（编号从 11 开始），最终可以确保每个样本成为答案的概率均为 \frac{1}{n}n1（其中 nn 为样本总数）。
容易证明该做法的正确性，假设最终成为答案的样本编号为 kk，那么 kk 成为答案的充要条件为「在遍历到 kk 时被选中」并且「遍历大于 kk 的所有元素时，均没有被选择（没有覆盖 kk）」。
对应事件概率为：
P = \frac{1}{k} * (1 - \frac{1}{k + 1}) * (1 - \frac{1}{k + 2}) * ... * (1 - \frac{1}{n})P=k1∗(1−k+11)∗(1−k+21)∗...∗(1−n1)
首项 \frac{1}{k}k1 为选中 kk 的概率，后面每项分别为编号为 [k + 1, n][k+1,n] 的样本 不被选中 的概率。
化简得：
P = \frac{1}{k} * \frac{k}{k + 1} * \frac{k + 1}{k + 2} * ... * \frac{n - 1}
{n}P=k1∗k+1k∗k+2k+1∗...∗nn−1
进一步抵消化简后，可得：
P = \frac{1}{n}P=n1
因此，在每一次 getRandom 时，从前往后处理每个节点，同时记录当前节点的编号，当处理到节点 kk 时，在 [0, k)[0,k) 范围内进行随机，若随机到结果为 00（发生概率为 \frac{1}{k}k1），则将节点 kk 的值存入答案，最后一次覆盖答案的节点即为本次抽样结果。
代码（感谢 @Benhao 同学提供的其他语言版本）：
class Solution { ListNode head; Random random = new Random(20220116); public Solution(ListNode _head) { head = _head; } public int getRandom() { int ans = 0, idx = 0; ListNode t = head; while (t != null && ++idx >= 0) { if (random.nextInt(idx) == 0) ans = t.val; t = t.next; } return ans; } } 复制代码
class Solution: def __init__(self, head: Optional[ListNode]): self.root = head def getRandom(self) -> int: node, ans, i = self.root, None, 0 while node: if not randint(0, i): ans = node.val node, i = node.next, i + 1 return ans 复制代码
type Solution struct { Root *ListNode } func Constructor(head *ListNode) Solution { return Solution{head} } func (this *Solution) GetRandom() (ans int) { for node, idx := this.Root, 1;node != nil; idx++ { if rand.Intn(idx) == 0{ ans = node.Val } node = node.Next } return } 复制代码
- 时间复杂度：令 nn 为链表长度，随机获取某个值的复杂度为 O(n)O(n)
- 空间复杂度：O(1)O(1)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.382 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
