蓄水池抽样算法

「蓄水池抽样算法」

优势:只需一次遍历,适用总量未知的情况

蓄水池抽样算法可以扩展很多应用范围,比如游戏的签到抽奖系统,在抽奖之前,你不知道参与的总人数。

对于一个池内,获取每个数字的概率都是一样的

  • 如果我们池子中只有一个数字,那么拿到第一个数字的概率就是100%毋庸置疑。
  • 两个数字50% 三个数字每个数字的几率都是33% 以此类推。。。。

当我们不知道池子里有多少个数字的时候,就需要用蓄水池的算法思想去计算。

  • 当链表前行到第一个数字,此时取第一个数字的几率为100%,那result自然等于这个数字。
  • 前进到第二个数字,那么此时取这个数字的几率自然就为50%(池子里只有两个数字),那么就是50%的几率取新数字,50%的几率保留原本的数字。
  • 第三个数字的时候,33%的几率取当前最新的这个数字,66%的几率保留原本的数字。这66%中:原本的数字有50%的几率是1,有50%的几率是2。也就是此时三个数字的概率都为33%。 通过这个算法,就能达到取数的概率均摊,从而实现随机。
//给你一个单链表,随机选择链表的一个节点,并返回相应的节点值。每个节点 被选中的概率一样 。
//
// 实现 Solution 类:
//
//
// Solution(ListNode head) 使用整数数组初始化对象。
// int getRandom() 从链表中随机选择一个节点并返回该节点的值。链表中所有节点被选中的概率相等。
class Solution {
    ListNode head;
    Random random = new Random();
    public Solution(ListNode _head) {
        random = new Random();
        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;
    }
}

为什么算法是正确可靠的?

蓄水池算法思想
假设现在有一个容量为N的袋子一个机器每次发出一个球问你如何使得最终发了任意颗球后所有球在袋子中的几率相等
实现方法
1.如果发出来的球的序号(count)小于等于N那么袋子还没装满直接丢进去就可以了
2.如果发出来的球的序号(count)大于N那么就以N/count的概率判断这个球是否入袋如果入袋就以1/N的概率随机淘汰掉袋子中的某个位置的球这里的袋子在代码实现中就是数组所以就是随机淘汰掉0~N-1下标位置的球
证明
为什么这样所有球在袋子的概率是相同的呢
1.机器发出的球数如果小于等于N那么很明显所有的球在袋子中的概率都是相等的为1,毋庸置疑
2.机器发出的球数如果大于N比如此时count=N+1问3号球在袋子中的概率
2.1此时N+1号球以N/(N+1)的概率入袋所以N+1号球在袋子中的概率就是N/(N+1)不管你淘汰哪个反正我是进去了
2.2此时3号球被淘汰的概率是N/(N+1)*1/N=1/(N+1)这个也好理解被淘汰这个事件由N+1能够进入袋子和1/N的概率正好
淘汰掉3号两个事件组成那么3号球存在袋子中的概率就是1-1/(N+1) = N/(N+1)这和N+1号球是相同的

我们选择的3号位置是随机的同理选择其他位置采用同样的计算方法也能得到1~N+1号球的概率都是相同的而且是N/(N+1)所以蓄水池算法正确

对于这道题目来说需要我们返回随机一个位置节点的值那么好嘛可以定义一个袋子假如这个袋子容量就是1那么每次从袋子中淘汰的概率都是1因为就一个元素所以必定淘汰它只要将所有节点都判断一遍最后袋子里剩下的不就是随机节点的值吗

作者vigilant-hermannoht
链接https://leetcode-cn.com/problems/linked-list-random-node/solution/xu-shui-chi-suan-fa-zheng-ming-wei-shi-y-xwzn/
来源力扣LeetCode
著作权归作者所有商业转载请联系作者获得授权非商业转载请注明出处
Licensed under CC BY-NC-SA 4.0
Last updated on Oct 04, 2024 04:07 UTC
让过去的过去,给时间点时间
Built with Hugo
Theme Stack designed by Jimmy