`

java-蓄水池抽样-要求从N个元素中随机的抽取k个元素,其中N无法确定

 
阅读更多
蓄水池抽样(Reservoir Sampling)
相关证明可看这个链接:http://www.cnblogs.com/HappyAngel/archive/2011/02/07/1949762.html
以下为上面这个链接的两个截图:





import java.util.Arrays;
import java.util.Random;


public class ReservoirSampling {

	/**
	 * 题目:给定一个数据流,其中包含无穷尽的搜索关键字(比如,人们在谷歌搜索时不断输入的关键字)。
	 * 如何才能从这个无穷尽的流中随机的选取1000个关键字?
	 * Reservoir Sampling
	 * I read some proof on the internet,but I found they are hard to understand except this:
	 * http://www.cnblogs.com/HappyAngel/archive/2011/02/07/1949762.html
	 * It's excellent.
	 */
	public static void main(String[] args) {
		int k=100;
		int n=1000;
		int[] data=new int[n];
		for(int i=0;i<n;i++){
			data[i]=i;
		}
		int[] sample=reservoirSampling(data,k);
		System.out.println(Arrays.toString(sample));
	}
	
	public static int[] reservoirSampling(int[] data,int k){
		if(data==null){
			return new int[0];//In <Effective Java>,it advises to return int[0] instead of null.Am i doing right in this case?
		}
		if(data.length<k){
			return new int[0];
		}
		int[] sample=new int[k];
		int n=data.length;
		for(int i=0;i<n;i++){
			if(i<k){
				sample[i]=data[i];
			}else{
				int j=new Random().nextInt(i);
				if(j<k){
					sample[j]=data[i];
				}
			}
		}
		return sample;
	}

}

  • 大小: 34.1 KB
  • 大小: 48.3 KB
1
0
分享到:
评论
1 楼 paul920531 2015-09-25  
39行有个bug:"int j=new Random().nextInt(i);" 改为"int j=new Random().nextInt(i+1);"

相关推荐

    蓄水池抽样

    这样,蓄水池中保留的 K 个元素将保持随机性。 3. **概率分析**: - 每个元素被选入蓄水池的概率可以通过归纳法证明是相等的。例如,当 i=k+1 时,第 k+1 个元素被选中的概率是 k/(k+1)。假设对于 i 的情况,前 i ...

    FZU-AI#AI_note#leetcode第三十八天-蓄水池抽样1

    今天完成题目:398print( random.uniform(1.1,5.4) ) # 产生 1.1 到 5.4 之间的随机浮点数,区间可以不是整数a=[1,

    蓄水池算法leetcode-randomized-algorithm:随机算法

    蓄水池算法leetcode 固定范围采样 输入大小为 n 个项目 获取 0 到 n -1 之间的随机数 根据输入返回项目[索引] 油藏取样 概括 n项的流 n不知道提前 每个项目结果的概率相等 算法 水库采样算法旨在从未知大小的总体中...

    建筑施工组织2021-蓄水池施工方案.docx

    ### 建筑施工组织2021-蓄水池施工方案 #### 1. 编制说明及编制依据 **1.1 编制说明** - **目的**:本施工方案旨在确保按照公司的质量方针,高效有序地完成蓄水池项目的施工任务,实现高质量、快速度与低成本的...

    参考资料-工业蓄水池施工方案.zip

    《工业蓄水池施工方案》是一份详细的指导性文件,主要针对在工业环境中建造蓄水池的全过程。蓄水池是工业生产中重要的基础设施之一,用于储存和调节水资源,以满足生产、消防、环保等多方面的需求。这份施工方案旨在...

    蓄水池算法leetcode-leetcode:leetcode

    蓄水池算法 leetcode leetcode Post: 《双指针的魅力》 《常见面试题思想方法整理》 TODO: 《深入理解双指针》 《再谈双指针》 《重新认识二级指针》 《Reservoir Sample - 蓄水池抽样》 Blog: 《结构之法 算法之道...

    蓄水池单元工程质量评定表--.pdf

    文档中的内容涉及的是一个蓄水池工程的质量评定过程,这是在教育领域中可能涉及的工程管理实践。这个蓄水池工程位于波密县寺庙饮水安全工程的范围内,由承包单位西藏恒欣建设工程有限公司负责实施。工程的具体工作...

    leetcode蓄水池JAVA-Algorithm-in-Java:算法学习日记

    蓄水池JAVA Java中的算法 进度: 2018 5/1 重温 Java 中的基本数据结构 7/18 LC 60 7/30 LC 100 8/5 LC 117 8/9 LC 130 8/14 LC 147 9/9 LC 176 2019年 5/29 LC 209 实现 BinaryIndexedTree。 7/31/18 位操作。 需要...

    EatApples#kaleidoscope#蓄水池抽样1

    (1)维护一个大小为 M 的数组. 记当前接收的是第 N 个数据(这里从 1 开始,代码中从 0 开始) (2)如果 N, 直接插入(对于前 M 个元素,

    leetcode蓄水池JAVA-coding-interview:面试中编码问题的学习笔记

    蓄水池JAVA 编程面试 学习资源 基本 复杂 数据结构 解决方案模式 问题模式 前 K 和 Kth 顶K 第 K 个 LeetCode-215 数组中第 K 大的元素 LeetCode-703 流中第 K 大的元素 LeetCode-BST 中第 230 K 个最小的元素 ...

    leetcode蓄水池JAVA-Leetcode:力码日志

    蓄水池JAVA 力码 旨在熟悉Java和python实现的算法和数据结构。 :) 如果你放弃,你只会输。 标签 大批 标题 解决方案 哈希表 标题 解决方案 链表 标题 解决方案 数学 标题 解决方案 细绳 标题 解决方案 两个指针 标题...

    蓄水池算法leetcode-leetcode-ts:leetcode-ts

    蓄水池算法,又称Reservoir Sampling,是一种在未知大小的大数据流中随机抽取固定数量样本的算法。在LeetCode平台上,这个算法常被用于解决实际编程挑战,例如处理大规模无序数据集的问题。这里我们主要探讨蓄水池...

    蓄水池施工方案.docx

    综上所述,蓄水池的施工方案涵盖了从前期准备、设计依据、工程特点到施工过程中的质量控制、安全措施、进度安排等多个方面,是全面指导施工活动的重要文件。在实际操作中,需根据现场实际情况适时调整,以确保工程按...

    某蓄水池施工组织设计方案.doc

    【某蓄水池施工组织设计方案】是一份详细指导蓄水池建设的工程文件...总结来说,这个蓄水池施工组织设计方案涵盖了从工程设计、施工流程、质量管理到安全控制的全面规划,旨在高效、安全且合规地完成蓄水池的建设工作。

    leetcode蓄水池JAVA-iq-notes:智商笔记

    蓄水池JAVA 智商笔记 日常编码问题#1.给定一个数字列表和一个数字 k,返回列表中的任意两个数字加起来是否为 k。 答:对数组进行排序。 从最左边的元素开始并将其添加到最后一个元素。 如果总和相等,则您找到了匹配...

    精品资料系列2021-05S804矩形钢筋凝土蓄水池图集.pdf

    根据给定文件信息,我们需要探讨的是关于“精品资料系列2021-05S804矩形钢筋混凝土蓄水池图集”的相关知识点。虽然提供的具体内容实际上并不包含实际的图集信息,我们仍然可以根据标题和描述来构建一个丰富的知识点...

    蓄水池蓄水试验记录表.doc

    这份文档记录了陇县天成镇张家山蓄水池管网工程中的蓄水池蓄水试验过程,包括1#蓄水池和3#蓄水池的试验细节,涉及到以下几个关键知识点: 1. **蓄水试验目的**: 蓄水试验的主要目的是验证蓄水池的密封性,检查...

    04S803 圆形钢筋溷凝土蓄水池图集.pdf

    圆形钢筋溷凝土蓄水池图集,04S803 圆形钢筋溷凝土蓄水池图集.pdf 04S803 圆形钢筋溷凝土蓄水池图集.pdf

    500蓄水池结构图

    500T蓄水池结构图、配筋图、平面布置图及钢筋明细表,很好用的

    百度:部分算法面试题1

    1. **蓄水池抽样**:在不知道元素总数的情况下,需要一次性遍历链表并随机抽取k个元素,保证每个元素被选中的概率相等。蓄水池抽样的策略是先选择前k个元素,然后对于剩余的元素,以k/i的概率替换已选中的一个元素。...

Global site tag (gtag.js) - Google Analytics