382. 链表随机节点 : 蓄水池抽样运用题

简介: 382. 链表随机节点 : 蓄水池抽样运用题

网络异常,图片无法展示
|

题目描述



这是 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^4104<=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(1k+11)(1k+21)...(1n1)


首项 \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=k1k+1kk+2k+1...nn1


进一步抵消化简后,可得:


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 原题链接和其他优选题解。

相关文章
|
1月前
|
算法
LeetCode第24题两两交换链表中的节点
这篇文章介绍了LeetCode第24题"两两交换链表中的节点"的解题方法,通过使用虚拟节点和前驱节点技巧,实现了链表中相邻节点的交换。
LeetCode第24题两两交换链表中的节点
|
1月前
|
Python
【Leetcode刷题Python】剑指 Offer 22. 链表中倒数第k个节点
Leetcode题目"剑指 Offer 22. 链表中倒数第k个节点"的Python解决方案,使用双指针法找到并返回链表中倒数第k个节点。
40 5
|
1月前
|
Python
【Leetcode刷题Python】剑指 Offer 18. 删除链表的节点
Leetcode题目"剑指 Offer 18. 删除链表的节点"的Python解决方案,通过使用双指针法找到并删除链表中值为特定数值的节点,然后返回更新后的链表头节点。
31 4
|
2月前
|
安全 云计算
云计算自旋锁问题之在线程安全地删除链表节点时,需要频繁加锁会影响性能如何解决
云计算自旋锁问题之在线程安全地删除链表节点时,需要频繁加锁会影响性能如何解决
37 2
|
4月前
|
存储 Python
删除链表节点详解
删除链表节点详解
|
3月前
|
算法
【数据结构与算法 刷题系列】求带环链表的入环节点(图文详解)
【数据结构与算法 刷题系列】求带环链表的入环节点(图文详解)
|
3月前
24. 两两交换链表中的节点
24. 两两交换链表中的节点
|
3月前
|
存储
删除链表的节点
删除链表的节点
23 0
|
3月前
|
存储 SQL 算法
|
3月前
|
SQL 算法 数据挖掘
力扣题目 19:删除链表的倒数第N个节点 【python】
力扣题目 19:删除链表的倒数第N个节点 【python】