「蓄水池抽样算法」

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

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

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

  • 如果我们池子中只有一个数字,那么拿到第一个数字的概率就是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)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

评论