LeetCode 382. 链表随机节点
题目描述
题意分析
每次调用
getRandom()，从链表中等概率选择一个节点并返回它的值。等概率针对节点，而不是不同的数值；如果多个节点的值相同，这个值被返回的概率应当包含所有这些节点的概率。进阶要求处理长度未知的大链表，并只使用常数额外空间。不能把所有节点存进数组后随机下标，因此需要在一次遍历中不断更新一个候选，使遍历结束时每个节点都有相同的机会留下。题目保证链表非空。
解法：水塘抽样
核心思路
[!blue]
使用容量为一的“水塘”：
answer保存当前选中的节点值，seen表示已经看过的节点数。希望始终保持一个不变量：看过seen个节点后，其中每个节点成为候选的概率都是1 / seen。最开始只看过头节点，所以直接令
answer = head.val、seen = 1，它以概率 $1$ 被选中。从第二个节点开始，每看到第i个节点，就以 $1/i$ 的概率用它替换当前候选，其余情况下保留原候选。为什么替换概率必须是 $1/i$？假设前
i - 1个节点已经等概率：
- 新节点只有在本轮替换时才能成为候选，因此它的概率是 $1/i$。
- 任意一个旧节点，原来成为候选的概率是 $1/(i-1)$，本轮还需要不被替换。两者相乘为 $\frac{1}{i-1}\times\frac{i-1}{i}=\frac{1}{i}$。
所以新旧节点在本轮结束后仍然等概率。由第一个节点开始归纳，遍历完
n个节点后，每个节点留下的概率就是 $1/n$，无需预先知道n。实现时，先将当前节点计入
seen，再在整数区间[0, seen)内均匀取一个随机数。这个区间有seen个整数，只有抽到 $0$ 才替换，因此替换概率正好是1 / seen。这里使用整数随机接口，不需要计算浮点概率。构造函数只保存头节点。每次
getRandom()都重新初始化候选和计数，从头完成一轮抽样；这样每次调用都满足同一份等概率证明。只有一个节点时无需抽随机数，直接返回它即可。
解题步骤
- 构造对象时保存
head。- 每次取样时，将头节点值设为
answer，将seen设为 $1$。- 从第二个节点开始遍历，先执行
seen++，再从[0, seen)中均匀取随机整数；抽到 $0$ 时将answer更新为当前节点值。- 到达链表末尾后，返回候选值
answer。
代码实现
class Solution {
private final ListNode head;
public Solution(ListNode head) {
this.head = head;
}
public int getRandom() {
// 每次调用重新开始一轮等概率采样
int answer = head.val;
int seen = 1;
for (ListNode node = head.next; node != null; node = node.next) {
// 先计入当前节点，再以已见数量的倒数决定替换
seen++;
if (ThreadLocalRandom.current().nextInt(seen) == 0) {
answer = node.val;
}
}
return answer;
}
}
import "math/rand"
type Solution struct {
head *ListNode
}
func Constructor(head *ListNode) Solution {
return Solution{head: head}
}
func (s *Solution) GetRandom() int {
// 每次调用重新开始一轮等概率采样
answer, seen := s.head.Val, 1
for node := s.head.Next; node != nil; node = node.Next {
// 先计入当前节点，再以已见数量的倒数决定替换
seen++
if rand.Intn(seen) == 0 {
answer = node.Val
}
}
return answer
}
复杂度分析
- 时间复杂度：构造为 $O(1)$，每次随机取样为 $O(n)$。
- 空间复杂度：$O(1)$，不保存节点数组。
关键点总结
[!green]
- 每一步都让已见节点等概率，而不只是让当前节点有机会被选中。
- 计数的是节点，不是不同值；相同节点值不影响抽样过程。
- 先增加计数，才能让当前节点获得正确的
1/seen概率；每次调用都重新开始计数。
易错点总结
[!yellow]
- 沿用上次调用的计数，会改变本轮采样概率。
- 先抽样再增加计数，第二个节点就会被错误地必选。
- 按不同值去重，会改变重复值应有的概率。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 398. 随机数索引 | 中等 | 同样在不知道匹配总量或不保存全部下标时做蓄水池抽样，保持已见候选等概率。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！