在一个文件中有10G个整数,乱序排列,要求找出中位数

 题目:在一个文件中有 10G 个整数,乱序排列,要求找出中位数。内存限制为 2G。只写出思路即可(内存限制为 2G的意思就是,可以使用2G的空间来运行程序,而不考虑这台机器上的其他软件的占用内存)。

关于中位数:数据排序后,位置在最中间的数值。即将数据分成两部分,一部分大于该数值,一部分小于该数值。中位数的位置:当样本数为奇数时,中位数=(N+1)/2 ; 当样本数为偶数时,中位数为N/2与1+N/2的均值(那么10G个数的中位数,就第5G大的数与第5G+1大的数的均值了)。

分析:明显是一道工程性很强的题目,和一般的查找中位数的题目有几点不同。
1. 原数据不能读进内存,不然可以用快速选择,如果数的范围合适的话还可以考虑桶排序或者计数排序,但这里假设是32位整数,仍有4G种取值,需要一个16G大小的数组来计数。

2. 若看成从N个数中找出第K大的数,如果K个数可以读进内存,可以利用最小或最大堆,但这里K=N/2,有5G个数,仍然不能读进内存。

3. 接上,对于N个数和K个数都不能一次读进内存的情况,《编程之美》里给出一个方案设k<K,且k个数可以完全读进内存,那么先构建k个数的堆,先找出第0到k大的数,再扫描一遍数组找出第k+1到2k的数,再扫描直到找出第K个数。虽然每次时间大约是nlog(k),但需要扫描ceil(K/k) 次,这里要扫描5次。(编程之美 寻找最大的K个数)

解法:首先假设是32位无符号整数。
1. 读一遍10G个整数,把整数映射到256M个区段中,用一个64位无符号整数给每个相应区段记数。
说明:整数范围是0 - 2^32 - 1,一共有4G种取值,映射到256M个区段,则每个区段有16(4G/256M = 16)种值,每16个值算一段, 0~15是第1段,16~31是第2段,……2^32-16 ~2^32-1是第256M段。一个64位无符号整数最大值是0~8G-1,这里先不考虑溢出的情况。总共占用内存256M×8B=2GB。

2. 从前到后对每一段的计数累加,当累加的和超过5G时停止,找出这个区段(即累加停止时达到的区段,也是中位数所在的区段)的数值范围,设为[a,a+15],同时记录累加到前一个区段的总数,设为m。然后,释放除这个区段占用的内存。

3. 再读一遍10G个整数,把在[a,a+15]内的每个值计数,即有16个计数。

4. 对新的计数依次累加,每次的和设为n,当m+n的值超过5G时停止,此时的这个计数所对应的数就是中位数。

总结:
1.以上方法只要读两遍整数,对每个整数也只是常数时间的操作,总体来说是线性时间。

2. 考虑其他情况。
若是有符号的整数,只需改变映射即可。若是64为整数,则增加每个区段的范围,那么在第二次读数时,要考虑更多的计数。若过某个计数溢出,那么可认定所在的区段或代表整数为所求,这里只需做好相应的处理。噢,忘了还要找第5G+1大的数了,相信有了以上的成果,找到这个数也不难了吧。

3. 时空权衡。
花费256个区段也许只是恰好配合2GB的内存(其实也不是,呵呵)。可以增大区段范围,减少区段数目,节省一些内存,虽然增加第二部分的对单个数值的计数,但第一部分对每个区段的计数加快了(总体改变??待测)。

4. 映射时尽量用位操作,由于每个区段的起点都是2的整数幂,映射起来也很方便。

题目:设计一个数据结构,包括两个函数,插入数据和获得中位数。

利用大根堆和小根堆,其中大根堆维护较小的一半数据,小根堆维护较大的一半数据。

然后根据相应的情况,对两个堆做相应的堆化操作,以满足两个堆中元素数目一致。时间复杂度O(lgn)

extension:

设计一个堆栈,除了常见的堆栈操作,还有一个返回中位数的操作。

同样利用大根堆和小根堆,来维护中位数。时间复杂度O(lgn)

时间: 03-15

在一个文件中有10G个整数,乱序排列,要求找出中位数的相关文章

10G 个整数,乱序排列,要求找出中位数。内存限制为 2G。

题目:在一个文件中有 10G 个整数,乱序排列,要求找出中位数.内存限制为 2G.只写出思路即可(内存限制为 2G的意思就是,可以使用2G的空间来运行程序,而不考虑这台机器上的其他软件的占用内存). 关于中位数:数据排序后,位置在最中间的数值.即将数据分成两部分,一部分大于该数值,一部分小于该数值.中位数的位置:当样本数为奇数时,中位数=(N+1)/2 ; 当样本数为偶数时,中位数为N/2与1+N/2的均值(那么10G个数的中位数,就第5G大的数与第5G+1大的数的均值了). 分析:明显是一道工

10G 个整数找出中位数,内存限制为 2G

题目:在一个文件中有 10G 个整数,乱序排列,要求找出中位数.内存限制为 2G.只写出思路即可(内存限制为 2G的意思就是,可以使用2G的空间来运行程序,而不考虑这台机器上的其他软件的占用内存). 关于中位数:数据排序后,位置在最中间的数值.即将数据分 成两部分,一部分大于该数值,一部分小于该数值.中位数的位置:当样本数为奇数时,中位数=(N+1)/2 ; 当样本数为偶数时,中位数为N/2与1+N/2的均值(那么10G个数的中位数,就第5G大的数与第5G+1大的数的均值了). 分析:明显是一道

Shell脚本实现乱序排列文件内容的多种方法(洗牌问题)

洗牌问题:洗一副扑克,有什么好办法?既能洗得均匀,又能洗得快?即相对于一个文件来说怎样高效率的实现乱序排列? ChinaUnix 确实是 Shell 高手云集的地方,只要你想得到的问题,到那里基本上都能找到答案.r2007给出了一个取巧的方法,利用 Shell 的 $RANDOM 变量给原文件的每一行加上随机的行号然后根据这个随机行号进行排序,再把临时加上去的行号给过滤掉,这样操作之后得到的新文件就相当于被随机“洗”了一次: while read i;do echo "$i $RANDOM&qu

shuf乱序排列

如何从文件中随即选取1000行内容呢?我们可以使用shuf命令 shuf [file] | head -n 1000 其中,shuf会读取file中的内容,并生成乱序的排列,进而使用head命令,取出前1000行 shuf乱序排列

AS3.0 扑克牌乱序排列法洗牌

package { /* *@ClassName:package::PokerMain *@Intro:这是一个初始化1-52扑克牌,然后进行乱序排列进行洗牌: *@Author:非若 *@Date:2015.07.22 *@LanguageVersion:ActionScript 3.0 * */ import flash.display.Sprite; public class PokerMain extends Sprite { //设置扑克牌总数 private var NUM:Numb

js数组乱序输出 数组乱序排列

网上看的数组乱序输出,要么不合实际,要么代码繁琐.自己试了下,希望能给大家带来帮助. 重要思想也是Math.random*arr.length随机下标,然后删除取到的元素,继续随机下标. //将数组乱序输出 var arr = [1,2,3,4,5,6,7,8,9,10]; var newArr = []; for(var i=0; i<arr.length; i++){ var index = Math.floor(Math.random()*arr.length);//随机下标 newArr

在一个SQL Server表中的多个列找出最大值

在一个SQL Server表中一行的多个列找出最大值 有时候我们需要从多个相同的列里(这些列的数据类型相同)找出最大的那个值,并显示 这里给出一个例子 IF (OBJECT_ID('tempdb..##TestTable') IS NOT NULL) DROP TABLE ##TestTable CREATE TABLE ##TestTable ( ID INT IDENTITY(1,1) PRIMARY KEY, Name NVARCHAR(40), UpdateByApp1Date DATE

codevs 1013 求先序排列(二叉树遍历)

传送门 Description 给出一棵二叉树的中序与后序排列.求出它的先序排列.(约定树结点用不同的大写字母表示,长度<=8). Input 两个字符串,分别是中序和后序(每行一个) Output 一个字符串,为二叉树的先序序列 Sample Input BADC BDCA Sample Output ABCD 思路 我们知道,前序遍历(PreOrder):根节点->左子树->右子树:中序遍历(InOrder):左子树->根节点->右子树:(PostOrder)后序遍历:左

codevs 1013 求先序排列 2001年NOIP全国联赛普及组 x

题目描述 Description 给出一棵二叉树的中序与后序排列.求出它的先序排列.(约定树结点用不同的大写字母表示,长度<=8). 输入描述 Input Description 两个字符串,分别是中序和后序(每行一个) 输出描述 Output Description 一个字符串,先序 样例输入 Sample Input BADC BDCA 样例输出 Sample Output ABCD 数据范围及提示 Data Size & Hint 分类标签 Tags 点此展开 #include<