算法篇-蓄水池算法

Myth丶恋晨 2022-09-11 11:21 192阅读 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 条评论，192人围观）

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

相关阅读

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

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

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

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

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

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

相关蓄水池算法

先看一道例题(智力题不用代码实现) 总共有1000个球和一个空间为十个球的袋子这一千个球一个一个的落出落出但是没进到袋子中的球永久丢失找不回来了保证每个球进入袋

爱被打了一巴掌/ 2023年10月12日 18:32/ 0 赞/ 29 阅读

相关软考算法-算法篇

软考算法一：故事背景二：分治法 2.1 概念 2.2 题目描述 2.3 代码实现 2.4 总结提升

柔光的暖阳◎/ 2023年10月10日 18:28/ 0 赞/ 37 阅读

相关 [算法]蓄水池抽样算法

问题背景： > 现有一个单链表，要求随机选择链表中的一个节点并返回节点值，并且保持链表中每个节点被选中的概率相同。刚看到这个问题，很多人肯定会很不屑：这有何难？先求得链表

Dear 丶/ 2023年06月25日 10:20/ 0 赞/ 9 阅读

相关算法篇-蓄水池算法

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

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

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

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

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

相关蓄水池算法

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

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

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

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

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

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

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

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