以在线处理的方式从一个长度未知的数据流中随机选出k个元素,注意点:
- 数据流长度未知,可能很大,所以不能先遍历保存成数组再取随机下标。
- 在线处理,边读取边计算结果。
- 不管数据规模有多大,取出的k个元素概率一样的。
蓄水池抽样的典型应用场景如下:
- 给定一个长度未知的单链表,请随机选择链表的一个节点,并返回相应的节点值。 要求每个节点被选中的概率都是一样的。
- 同上,但要求随机选出m个结点,同样要求每个节点被选中的概率都一样。
解决方法:
先以随机选出1个结点为例,第一次抽样时,选中该结点的概率为1,第二次抽样时,有1/2的概率将第二次抽样的值作为选中的结点,第三次抽样时,选中的概率为1/3,以此类推,遍历完所有的结点,最后保留的结点就是符合要求的随机结点,以单链表为例,示例代码如下:
int getRandom(ListNode *head) { int ans; int i = 0; for(auto node = head; node != nullptr; node = node->next) { if(rand() % i == 0) { // 第i个结点选中的概率为1/i,如果命中 ans = node->val; } i++; } return ans; }