算法-概率问题

2022-06-09 2022-09-04 约 270 字预计阅读 1 分钟

警告

本文最后更新于 2022-09-04，文中内容可能已过时。

1.基础

水塘抽样

$$ \begin{aligned} P &= P(第i个节点的值成为最后被返回的值) \newline &= P(第i次随机选择的值=0) \times P(第i+1次随机选择的值 \ne 0) \times \cdots \times P(第n次随机选择的值 \ne 0) \newline &= \frac{1}{i} \times (1-\frac{1}{i+1}) \times \cdots \times (1-\frac{1}{n}) \newline &= \frac{1}{i} \times \frac{i}{i+1} \times \cdots \times \frac{n-1}{n} \newline &= \frac{1}{n} \end{aligned} $$

2.实战

非重叠矩形中的随机点

497. 非重叠矩形中的随机点

🟨链表随机节点

382. 链表随机节点

水塘抽样

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    ListNode head;
    Random random;

    public Solution(ListNode head) {
        this.head = head;
        random = new Random();
    }

    public int getRandom() {
        int i = 1;
        int ans = 0;
        for (ListNode node = head; node != null; node = node.next) {
            // 1/i 的概率选中（替换为答案）
            if (random.nextInt(i) == 0) ans = node.val;
            ++i;
        }
        return ans;
    }
}

参考

链表随机节点 - 链表随机节点 - 力扣（LeetCode）

目录

算法-概率问题

1.基础

水塘抽样

2.实战

非重叠矩形中的随机点

🟨链表随机节点

参考