蓄水池抽样(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
分享到:
相关推荐
今天完成题目:398print( random.uniform(1.1,5.4) ) # 产生 1.1 到 5.4 之间的随机浮点数,区间可以不是整数a=[1,
蓄水池抽样 均匀抽样蓄水池抽样 均匀抽样
建筑施工组织2021-蓄水池施工方案.docx
参考资料-工业蓄水池施工方案.zip
蓄水池算法 leetcode leetcode Post: 《双指针的魅力》 《常见面试题思想方法整理》 TODO: 《深入理解双指针》 《再谈双指针》 《重新认识二级指针》 《Reservoir Sample - 蓄水池抽样》 Blog: 《结构之法 算法之道...
蓄水池算法leetcode 固定范围采样 输入大小为 n 个项目 获取 0 到 n -1 之间的随机数 根据输入返回项目[索引] 油藏取样 概括 n项的流 n不知道提前 每个项目结果的概率相等 算法 水库采样算法旨在从未知大小的总体中...
蓄水池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 位操作。 需要...
(1)维护一个大小为 M 的数组. 记当前接收的是第 N 个数据(这里从 1 开始,代码中从 0 开始) (2)如果 N, 直接插入(对于前 M 个元素,
蓄水池JAVA 编程面试 学习资源 基本 复杂 数据结构 解决方案模式 问题模式 前 K 和 Kth 顶K 第 K 个 LeetCode-215 数组中第 K 大的元素 LeetCode-703 流中第 K 大的元素 LeetCode-BST 中第 230 K 个最小的元素 ...
蓄水池JAVA 力码 旨在熟悉Java和python实现的算法和数据结构。 :) 如果你放弃,你只会输。 标签 大批 标题 解决方案 哈希表 标题 解决方案 链表 标题 解决方案 数学 标题 解决方案 细绳 标题 解决方案 两个指针 标题...
蓄水池单元工程质量评定表--.pdf
蓄水池JAVA 智商笔记 日常编码问题#1.给定一个数字列表和一个数字 k,返回列表中的任意两个数字加起来是否为 k。 答:对数组进行排序。 从最左边的元素开始并将其添加到最后一个元素。 如果总和相等,则您找到了匹配...
500T蓄水池结构图、配筋图、平面布置图及钢筋明细表,很好用的
圆形钢筋溷凝土蓄水池图集,04S803 圆形钢筋溷凝土蓄水池图集.pdf 04S803 圆形钢筋溷凝土蓄水池图集.pdf
建筑施工组织2021-中化蓄水池施工方案.doc
蓄水池施工方案.docx
蓄水池JAVA 介绍 Java 语言中 LeetCode 问题的个人解决方案。 试图涵盖针对一个问题的多种解决方案。 编码环境:VS Code 和 LeetCode 插件。 已解决问题列表 1 数据结构 1.1 数组 二分法(二分搜索)相关: 34 35 69...
leetcode蓄水池JAVA xiao-leetcode leet code src code, from easy to medium to hard, hahaha array backtracking(回溯) bit_manipulation breadth_first_search(深度优先遍历) depth_first_search(广度优先遍历) ...
leetcode蓄水池JAVA LeetCode 基于Java的leetcode解题记录 争取把所有leetcode的题都解完,部分题可能有多种解法 1. Folder description Folder Description problem 内含对问题题干描述的md文件 Including markdown...
给排水燃气施工组织设计-某蓄水池施工组织设计方案