算法篇-蓄水池算法

Myth丶恋晨 2022-09-11 11:21 148阅读 0赞

蓄水池算法：解决随机采样问题，每个元素被采样的概率相等

leetcode题目：https://leetcode-cn.com/problems/linked-list-random-node/submissions/

代码：

class Solution {
        // 蓄水池算法，随机从n个元素里取k个
        // 1.前k个元素入数组int[k]
        // 2.后面第i个（i >= k), k/(i + 1)概率替换 int[k]中一个-----------i从0开始
        // 3.遍历一次后，int[k]即为随机采样出来的
        private Random random;
        private ListNode head;
    
        /** @param head The linked list's head.
            Note that the head is guaranteed to be not null, so it contains at least one node. */
        public Solution(ListNode head) {
            this.head = head;
            this.random = new Random();
        }
        
        /** Returns a random node's value. */
        public int getRandom() {
            int ans = head.val;
            ListNode cur = head.next;
            int k = 2;
            while (cur != null) {
                if (random.nextInt(k++) == 0) {
                    ans = cur.val;
                }
                cur = cur.next;
            }
            return ans;
        }
    }

# 参考 #

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeWRmaW5k_size_20_color_FFFFFF_t_70_g_se_x_16]

证明过程请看下面连接  
————————————————  
版权声明：本文为CSDN博主「wwxy261」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。  
原文链接：https://blog.csdn.net/wwxy1995/article/details/102974566

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeWRmaW5k_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/c1f6f87d29d24ef3bfcdd50716292661.png

发表评论取消回复

表情：

评论列表（有 0 条评论，148人围观）

还没有评论，来说两句吧...

相关阅读

相关【算法&数据结构体系篇class29】：bfprt算法、蓄水池算法

一、bfprt算法时间复杂度O(N) > 在前面写过一篇排序算法[快排算法中，我们优化版本随机快排+荷兰国旗技巧优化][Link 1] ，其中我们优化核心点就是把划分

心已赠人/ 2024年03月23日 14:43/ 0 赞/ 37 阅读

相关 Python编程：实现蓄水池抽样算法 - 附完整代码

Python编程：实现蓄水池抽样算法 - 附完整代码蓄水池抽样算法是一种用于随机抽取固定大小样本的算法，该算法最初应用于从恒星数据库中随机抽取天文数据。随着时间的推移，该算

ゞ浴缸里的玫瑰/ 2024年03月16日 21:13/ 0 赞/ 23 阅读

相关算法篇-排序算法-冒泡排序

前言为了给自己关于算法部分·做一个系统的学习认知，同时也方便大家面试及工作，特此写这一部分的记录，记录自己的理解，一起学习，一起加油。一、关于排序算法中的冒泡排序

怼烎@/ 2024年02月05日 23:52/ 0 赞/ 16 阅读

相关【算法系列篇】模拟算法

![在这里插入图片描述][3a33fb0a3c6d418caed293acec4b7d94.gif_pic_center] 文章目录前言 1.替换所

今天药忘吃喽~/ 2023年10月15日 15:14/ 0 赞/ 1 阅读

相关算法篇-蓄水池算法

蓄水池算法：解决随机采样问题，每个元素被采样的概率相等 leetcode题目：https://leetcode-cn.com/problems/linked-list-ran

Myth丶恋晨/ 2022年09月11日 11:21/ 0 赞/ 149 阅读

相关算法开始篇

这系列博客主要记录自己学习《算法：c语言实现》的过程。主要参考： 1、Robert Sedgewick普林斯顿大学公开课，[课程链接见B站][B]。 2、算法：Ja

柔光的暖阳◎/ 2022年06月04日 03:37/ 0 赞/ 168 阅读

相关随机抽样算法：蓄水池抽样

![这里写图片描述][70] 1. 先选取数据流中的前k个元素，保存在集合A中； 2. 从第j（k + 1 <= j <= n）个元素开始，每次先以概率p = k/j选择

朴灿烈づ我的快乐病毒、/ 2022年05月30日 01:23/ 0 赞/ 181 阅读

相关蓄水池算法

![20180402102546954][] //蓄水池算法 public class CollectionA{ //一个简单的随机函数，决定一件

忘是亡心i/ 2022年05月27日 20:36/ 0 赞/ 149 阅读

相关算法题目——蓄水池问题

![1536313650228ab52a8ce6b][] 题目：给出了指定高度的任意两个板子，每个木板位置间隔相等，由你随机组合，怎么实现装最多的水。分析：假设水池厚度

秒速五厘米/ 2022年05月12日 07:44/ 0 赞/ 190 阅读

相关【搞定算法】蓄水池算法

1、问题描述分析采样问题经常会被遇到，比如： > 1、从 100000 份调查报告中抽取 1000 份进行统计； > 2、从一本很厚的电话簿中抽取 1000 人进

桃扇骨/ 2021年12月14日 13:37/ 0 赞/ 207 阅读