382. 链表随机节点

Difficulty
Medium
Tags
随机算法
URL
https://leetcode-cn.com/problems/linked-list-random-node/
Star
给你一个单链表，随机选择链表的一个节点，并返回相应的节点值。每个节点 被选中的概率一样 。
实现 Solution 类：
  • Solution(ListNode head) 使用整数数组初始化对象。
  • int getRandom() 从链表中随机选择一个节点并返回该节点的值。链表中所有节点被选中的概率相等。
示例：
notion imagenotion image
输入
["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, 104] 内
  • 104 <= Node.val <= 104
  • 至多调用 getRandom 方法 104 次
进阶：
  • 如果链表非常大且长度未知，该怎么处理？
  • 你能否在不使用额外空间的情况下解决此问题？

法1 暴力解

思路
遍历一遍链表，将值保存到数组中，然后随机返回一个
题解
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:

    def __init__(self, head: Optional[ListNode]):
        self.nodes = []
        while head:
            self.nodes.append(head.val)
            head = head.next


    def getRandom(self) -> int:
        return self.nodes[randint(0, len(self.nodes)-1)]

# Your Solution object will be instantiated and called as such:
# obj = Solution(head)
# param_1 = obj.getRandom()

法1 蓄水池抽样

思路
整理题意：总的样本数量未知，从所有样本中抽取若干个，要求每个样本被抽到的概率相等。
具体做法为：从前往后处理每个样本，每个样本成为答案的概率为 ，其中 为样本编号（编号从 开始），最终可以确保每个样本成为答案的概率均为（其中 为样本总数）。
容易证明该做法的正确性，假设最终成为答案的样本编号为 ，那么 成为答案的充要条件为「在遍历到 时被选中」并且「遍历大于 的所有元素时，均没有被选择（没有覆盖 ）」。
对应事件概率为：
首项 为选中 的概率，后面每项分别 为编号为 的样本不被选中的概率。
化简得：
因此，在每一次 getRandom 时，从前往后处理每个节点，同时记录当前节点的编号，当处理到节点 时，在 范围内进行随机，若随机到结果为 （发生概率），则将节点 的值存入答案，最后一次覆盖答案的节点即为本次抽样结果。
题解
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:

    def __init__(self, head: Optional[ListNode]):
        self.root = head

    def getRandom(self) -> int:
        res = None
        i = 0
        cur = self.root

        while cur:
            # 如果当前被选中了，更新结果
            if randint(0, i) == i:  # 这里不一定要 == i ,只需要表达此处的概率为 1/i 即可
                res = cur.val
            cur = cur.next
            i += 1
        return res

# Your Solution object will be instantiated and called as such:
# obj = Solution(head)
# param_1 = obj.getRandom()