LeetCode 382. Linked List Random Node 题解

LeetCode 382. Linked List Random Node 题解题目描述给你一个单链表随机选择链表的一个节点并返回相应的节点值。每个节点被选中的概率一样。实现 Solution 类Solution(ListNode head) 使用整数数组初始化对象。int getRandom() 从链表中随机选择一个节点并返回该节点的值。链表中所有节点被选中的概率相等。示例 1输入 [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 中的一个每个元素被返回的概率相等解题思路这是一个经典的蓄水池抽样Reservoir Sampling问题。蓄水池抽样算法当只有 1 个元素时选择它的概率是 1当有 2 个元素时以 1/2 的概率选择第 2 个元素否则保留第 1 个当有 n 个元素时以 1/n 的概率选择第 n 个元素否则保留之前的选择这样每个元素被选中的概率都是 1/n。代码实现import random class ListNode: def __init__(self, val0, nextNone): self.val val self.next next class Solution: def __init__(self, head): self.head head def getRandom(self): result 0 current self.head i 1 while current: # 以 1/i 的概率选择当前节点 if random.randint(1, i) 1: result current.val current current.next i 1 return result复杂度分析时间复杂度初始化O(1)getRandomO(n)需要遍历整个链表空间复杂度O(1)只使用了常数额外空间数学证明为什么每个节点被选中的概率都是 1/n对于第 k 个节点第 k 个节点被选中的概率是 1/k之后每个节点都没有替换它的概率是 (k/(k1)) × ((k1)/(k2)) × ... × ((n-1)/n) k/n所以第 k 个节点最终被选中的概率是(1/k) × (k/n) 1/n优化存储数组如果 getRandom 被频繁调用可以预先存储所有节点值import random class Solution: def __init__(self, head): self.values [] current head while current: self.values.append(current.val) current current.next def getRandom(self): return random.choice(self.values)时间复杂度初始化O(n)getRandomO(1)空间复杂度O(n)测试案例# 创建链表: 1 - 2 - 3 head ListNode(1, ListNode(2, ListNode(3))) solution Solution(head) # 测试随机性 results [solution.getRandom() for _ in range(10000)] counts {} for r in results: counts[r] counts.get(r, 0) 1 # 每个数字出现的次数应该接近 3333 print(counts)总结本题是蓄水池抽样算法的经典应用。关键点蓄水池抽样以 1/i 的概率选择第 i 个元素数学证明每个元素最终被选中的概率都是 1/n时间-空间权衡可以预先存储所有值来优化查询通过本题可以深入理解蓄水池抽样算法在大数据流处理中的应用。