题目:有一个很大很大的输入流,大到没有存储器可以将其存储下来,且只输入一次,如何从这个输入流中随机取得m个记录。
我的思路:
首先,存储开始的m条记录,存放于数组result[m]中;
然后,假设有n条记录,每一次读取记录后,取随机数x,0<= x < n;
判断随机数,
当0<= x < m时,我们将记录存放到result[x]中;
当m<= x < n时,我们不存这个记录;
最后,输入所有的数据流后,result[m]存放的就是随机出来的m条记录。
分析下,我们期待的某一个记录被选中的概率为m/n,按照我的这个算法,第i个记录被选中的事件可以描述成“该记录被选在数组里并且后面的记录都没有替代这个位置”,概率为
p = m/n * (1- 1/n)^(n-m-i)
很显然,这个对于所有的i,这个值都是趋近于m/n的。算法结果应该是正确的。
欢迎踊跃拍砖!
//==========================================更正
重新想了想,这个方法不是绝对公平的随机,每个数被选中的概率不是都相等,正如回复中说的,前m个数的P一样,对于后来的数,P越来越大。
欢迎提出新办法!
相关推荐
书中详细介绍了当前流行的论题和新的变化,讨论了算法设计技巧,并在研究算法的性能、效率以及对运行时间分析的基础上考查了一些高级数据结构,从历史的角度和近年的进展对数据结构的活跃领域进行了简要的概括。...
本文针对互联网消费金融的小额贷款申请,探讨机器学习技术在这个领域中 的发展情况和实际应用情况,研究违约用户和履约用户这两批用户的各方面特征, 介绍了在信用风险评估领域比较流行的Logistic回归模型和GBDT...
——加菲劳 《数据结构与算法分析》 ――课程内容体系主要内容 教学单元模块 具体教学内容 绪论 绪论部分是全书的预备知识,主要对ADL语言、数据结构与算法、算法分析基础、OOP、和C++做了简单介绍 基本数据结构 ...
《C#全能速查宝典》共分为8章,分别介绍了C#语言基础、Windows窗体及常用控件、Windows高级控件、控件公共属性、方法及事件、数据库开发、文件、数据流与注册表、GDI+绘图技术和C#高级编程,共包含562个C#编程中常用...
动态数据流具有数据量大、变化快、随机存取代价高、详细数据难以存储等特点,挖掘动态数据流对计算能力与存储能力要求非常高。针对动态数据流的以上特点,设计了一种基于自助抽样的动态数据流贝叶斯分类算法,算法...
本书是数据结构和算法分析的经典教材,书中使用主流的程序设计语言C++作为具体的实现语言。书的内容包括表、栈、队列、树、散列表、优先队列、排序、不相交集算法、图论算法、算法分析、算法设计、摊还分析、查找...
《数据结构与算法分析:Java语言描述(第2版)》是国外数据结构与算法分析方面的经典教材,使用卓越的Java编程语言作为实现工具讨论了数据结构(组织大量数据的方法)和算法分析(对算法运行时间的估计)。...
不相交集ADT8.1 等价关系8.2 动态等价性问题8.3 基本数据结构8.4 灵巧求并算法8.5 路径压缩8.6 按秩求并和路径压缩的最坏情形8.6.1 Union/Find算法分析8.7 一个应用总结练习参考文献第9章 图论算法9.1 若干定义9.1.1...
江 鹏 -《从一道题目的解法试谈网络流的构造与算法》 刘汝佳 -《搬运工问题的启示》 李益明 -《计算几何的相关问题》 李 源 -《树的枚举》 骆 骥 -《由"汽车问题"浅谈深度搜索的一个方面——搜索对象与策略的...
不相交集类8.1 等价关系8.2 动态等价性问题8.3 基本数据结构8.4 灵巧求并算法8.5 路径压缩8.6 路径压缩和按秩求并的最坏情形8.7 一个应用小结练习题参考文献第9章 图论算法9.1 若干定义9.2 拓扑排序9.3 最短路径...
不相交集类8.1 等价关系8.2 动态等价性问题8.3 基本数据结构8.4 灵巧求并算法8.5 路径压缩8.6 路径压缩和按秩求并的最坏情形8.7 一个应用小结练习题参考文献第9章 图论算法9.1 若干定义9.2 拓扑排序9.3 最短路径算法...
《算法导论》原书名——《Introduction to Algorithms》,是一本十分经典的计算机算法书籍,与高德纳(Donald E.Knuth)的《计算机程序设计艺术》(《The Art Of Computer Programming》)相媲美。 《算法导论》由...
2.返回x的二进制表示中从低到高的第i位 3.模取幂运算 4.求解模线性方程 5.求解模线性方程组(中国余数定理) 6.筛法素数产生器 7.判断一个数是否素数 图论: 1.Prim算法求最小生成树 2.Dijkstra算法求单源...
不相交集类8.1 等价关系8.2 动态等价性问题8.3 基本数据结构8.4 灵巧求并算法8.5 路径压缩8.6 路径压缩和按秩求并的最坏情形8.7 一个应用小结练习题参考文献第9章 图论算法9.1 若干定义9.2 拓扑排序9.3 最短路径算法...
本课件是一个动态演示数据结构算法执行过程的辅助教学软件, 它可适应读者对算法的输入数据和过程执行的控制方式的不同需求, 在计算机的屏幕上显示算法执行过程中数据的逻辑结构或存储结构的变化状况或递归算法执行...
本课件是一个动态演示数据结构算法执行过程的辅助教学软件, 它可适应读者对算法的输入数据和过程执行的控制方式的不同需求, 在计算机的屏幕上显示算法执行过程中数据的逻辑结构或存储结构的变化状况或递归算法执行...
*3.4.2 在输入流与输出流中使用控制符 3.4.3 用getchar和putchar函数进行字符的输入和输出 3.4.4 用scanf和printf函数进行输入和输出 3.5 编写顺序结构的程序 3.6 关系运算和逻辑运算 3.6.1 关系运算和关系表达式 ...