本文主要是介绍水塘抽样算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
水塘抽样算法
1、问题描述
最近经常能看到面经中出现在大数据流中的随机抽样问题
即:当内存无法加载全部数据时,如何从包含未知大小的数据流中随机选取k个数据,并且要保证每个数据被抽取到的概率相等。
假设数据流含有N个数,我们知道如果要保证所有的数被抽到的概率相等,那么每个数抽到的概率应该为 1/N
那如何保证呢?
2、解题思路
先说方案:
每次只保留一个数,当遇到第 i 个数时,以 1/i的概率保留它,(i-1)/i的概率保留原来的数。
举例说明: 1 - 10
- 遇到1,概率为1,保留第一个数。
- 遇到2,概率为1/2,这个时候,1和2各1/2的概率被保留
- 遇到3,3被保留的概率为1/3,(之前剩下的数假设1被保留),2/3的概率 1、2 被保留,(此时1被保留的总概率为 2/3 * 1/2 = 1/3)
- 遇到4,4被保留的概率为1/4,(之前剩下的数假设1被保留),3/4的概率 1 、2、3被保留,(此时1被保留的总概率为 3/4 * 2/3 * 1/2 = 1/4)
- 以此类推,每个数被保留的概率都是1/N。
3、示例
382. 链表随机节点
import random
class Solution:def __init__(self, head: ListNode):self.head = headdef getRandom(self) -> int:count = 0reserve = 0cur = self.headwhile cur:count += 1rand = random.randint(1,count)if rand == count:reserve = cur.valcur = cur.nextreturn reserve
参考资料
https://leetcode.cn/problems/linked-list-random-node/solutions/135440/xu-shui-chi-chou-yang-suan-fa-by-jackwener/
这篇关于水塘抽样算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!