帝国cms做的网站,网站建设服务范围,郑州高端网站开发,广州市招投标交易中心水塘抽样算法
1、问题描述
最近经常能看到面经中出现在大数据流中的随机抽样问题
即#xff1a;当内存无法加载全部数据时#xff0c;如何从包含未知大小的数据流中随机选取k个数据#xff0c;并且要保证每个数据被抽取到的概率相等。
假设数据流含有N个数#xff0c;我…水塘抽样算法
1、问题描述
最近经常能看到面经中出现在大数据流中的随机抽样问题
即当内存无法加载全部数据时如何从包含未知大小的数据流中随机选取k个数据并且要保证每个数据被抽取到的概率相等。
假设数据流含有N个数我们知道如果要保证所有的数被抽到的概率相等那么每个数抽到的概率应该为 1/N
那如何保证呢
2、解体思路
先说方案
每次只保留一个数当遇到第 i 个数时以 1/i的概率保留它(i-1)/i的概率保留原来的数。
举例说明 1 - 10
遇到1概率为1保留第一个数。遇到2概率为1/2这个时候1和2各1/2的概率被保留遇到33被保留的概率为1/3(之前剩下的数假设1被保留)2/3的概率 1 被保留(此时1被保留的总概率为 2/3 * 1/2 1/3)遇到44被保留的概率为1/4(之前剩下的数假设1被保留)3/4的概率 1 被保留(此时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/
