「蓄水池抽样算法」
优势：只需一次遍历，适用总量未知的情况
蓄水池抽样算法可以扩展很多应用范围，比如游戏的签到抽奖系统，在抽奖之前，你不知道参与的总人数。
对于一个池内，获取每个数字的概率都是一样的
- 如果我们池子中只有一个数字，那么拿到第一个数字的概率就是100%毋庸置疑。
- 两个数字50% 三个数字每个数字的几率都是33% 以此类推。。。。
当我们不知道池子里有多少个数字的时候，就需要用蓄水池的算法思想去计算。
- 当链表前行到第一个数字，此时取第一个数字的几率为100%，那result自然等于这个数字。
- 前进到第二个数字，那么此时取这个数字的几率自然就为50%（池子里只有两个数字），那么就是50%的几率取新数字，50%的几率保留原本的数字。
- 第三个数字的时候，33%的几率取当前最新的这个数字，66%的几率保留原本的数字。这66%中：原本的数字有50%的几率是1，有50%的几率是2。也就是此时三个数字的概率都为33%。 通过这个算法，就能达到取数的概率均摊，从而实现随机。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| 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;
}
}
|
为什么算法是正确可靠的？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| 蓄水池算法思想：
假设现在有一个容量为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）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
|