从海量数据中找出中位数

转自：http://hi.baidu.com/mcgrady32303/item/d652f2cb886be33498b49834

 

题目和基本思路都来源网上，本人加以整理。

题目：在一个文件中有 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次。

解法：首先假设是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的整数幂，映射起来也很方便。

 

 

然后线面帖的是拎一个人的，原文地址：

http://hi.baidu.com/taney/blog/item/3afd11dde5391bd38c102936.html

有12个小球,外形相同,其中一个小球的质量与其他11个不同 
给一个天平,问如何用3次把这个小球找出来 
并且求出这个小球是比其他的轻还是重解答:哈哈，据说这是微软前几年的一个面试题。很经典滴啊！三次一定能求出来，而且能确定是重还是轻。 
数据结构的知识还没怎么学透，不过这个题我到是自己研究过，可以分析下。 
将12个球分别编号为a1,a2,a3.......a10,a11,a12. 
第一步：将12球分开3拨，每拨4个，a1~a4第一拨，记为b1， a5~a6第2拨，记为b2，其余第3拨，记为b3； 
第二步：将b1和b2放到天平两盘上，记左盘为c1，右为c2；这时候分两中情况： 

1.c1和c2平衡，此时可以确定从a1到a8都是常球；然后把c2拿空，并从c1上拿下a4，从a9到a12四球里随便取三球，假设为a9到a11，放到c2上。此时c1上是a1到a3，c2上是a9到a11。从这里又分三种情况： 
      A：天平平衡，很简单，说明没有放上去的a12就是异球，而到此步一共称了两次，所以将a12随便跟11个常球再称一次，也就是第三次，马上就可以确定a12是重还是轻； 
      B： 若c1上升，则这次称说明异球为a9到a11三球中的一个，而且是比常球重。取下c1所有的球，并将a8放到c1上，将a9取下，比较a8和a11（第三 次称），如果平衡则说明从c2上取下的a9是偏重异球，如果不平衡，则偏向哪盘则哪盘里放的就是偏重异球； 
      C：若c1下降，说明a9到a11里有一个是偏轻异球。次种情况和B类似，所以接下来的步骤照搬B就是； 

2.c1和c2不平衡，这时候又分两种情况，c1上升和c1下降，但是不管哪种情况都能说明a9到a12是常球。这步是解题的关键。也是这个题最妙的地方。 
      A：c1上升，此时不能判断异球在哪盘也不能判断是轻还是重。取下c1中的a2到a4三球放一边，将c2中的a5和a6放到c1上，然后将常球a9放到c2上。至此，c1上是a1，a5和a6，c2上是a7，a8和a9。此时又分三中情况： 
          1） 如果平衡，说明天平上所有的球都是常球，异球在从c1上取下a2到a4中。而且可以断定异球轻重。因为a5到a8都是常球，而第2次称的时候c1是上升 的，所以a2到a4里必然有一个轻球。那么第三次称就用来从a2到a4中找到轻球。这很简单，随便拿两球放到c1和c2，平衡则剩余的为要找球，不平衡则 哪边低则哪个为要找球； 
          2）c1仍然保持上升，则说明要么a1是要找的轻球， 要么a7和a8两球中有一个是重球（这步懂吧？好好想想，很简单的。因为a9是常球，而取下的a2到a4肯定也是常球，还可以推出换盘放置的a5和a6也 是常球。所以要么a1轻，要么a7或a8重）。至此，还剩一次称的机会。只需把a7和a8放上两盘，平衡则说明a1是要找的偏轻异球，如果不平衡，则哪边 高说明哪个是偏重异球； 
          3）如果换球称第2次后天平平衡打破，并且c1降低了，这说明异球肯定在换过来的a5和a6两求中，并且异球偏重，否则天平要么平衡要么保持c1上升。确定要找球是偏重之后，将a5和a6放到两盘上称第3次根据哪边高可以判定a5和a6哪个是重球； 
      B： 第1次称后c1是下降的，此时可以将c1看成c2，其实以后的步骤都同A，所以就不必要再重复叙述了。至此，不管情况如何，用且只用三次就能称出12个外 观手感一模一样的小球中有质量不同于其他11球的偏常的球。而且在称的过程中可以判定其是偏轻还是偏重。
给一个奇数阶N幻方，填入数字1，2，3...N*N,使得横竖斜方向上的和都相同答案:#include<iostream>#include<iomanip>#include<cmath>usingnamespace std;int main(){int n; cin>>n;int i;int **Matr=newint*[n];//动态分配二维数组for(i=0;i<n;++i)      Matr[ i ]=newint[n];//动态分配二维数组 //j=n/2代表首行中间数作为起点，即1所在位置int j=n/2,num=1;//初始值 i=0;while(num!=n*n+1) {//往右上角延升，若超出则用%转移到左下角      Matr[(i%n+n)%n][(j%n+n)%n]=num;    //斜行的长度和n是相等的，超出则转至下一斜行    if(num%n==0)          i++;   else      {          i--;          j++;     }      num++; }for(i=0;i<n;i++) {      for(j=0;j<n;++j)         cout<<setw((int)log10(n*n)+4)<<Matr[ i][ j ];//格式控制      cout<<endl<<endl;//格式控制 }for(i=0;i<n;++i)      delete [ ]Matr[ i ];return1;}腾讯的一道面试题:(与百度相似,可惜昨天百度死在这方面了)////在一个文件中有 10G 个整数，乱序排列，要求找出中位数。内存限制为 2G。只写出思路即可。答案:1， 把整数分成256M段，每段可以用64位整数保存该段数据个数，256M*8 = 2G内存，先清0 
2，读10G整数，把整数映射到256M段中，增加相应段的记数 
3，扫描256M段的记数，找到中位数的段和中位数的段前面所有段的记数，可以把其他段的内存释放 
4，因中位数段的可能整数取值已经比较小（如果是32bit整数，当然如果是64bit整数的话，可以再次分段），对每个整数做一个记数，再读一次10G整数，只读取中位数段对应的整数，并设置记数。 
5，对新的记数扫描一次，即可找到中位数。 
如果是32bit整数，读10G整数2次，扫描256M记数一次，后一次记数因数量很小，可以忽略不记(设是32bit整数，按无符号整数处理 
整数分成256M段？ 整数范围是0 - 2^32 - 1 一共有4G种取值，4G/256M = 16，每16个数算一段 0-15是1段，16-31是一段，... 
整数映射到256M段中？ 如果整数是0-15，则增加第一段记数，如果整数是16-31，则增加第二段记数，... 

其实可以不用分256M段，可以分的段数少一写，这样在扫描记数段时会快一些，还能节省一些内存)

腾讯题二:一个文件中有40亿个整数，每个整数为四个字节，内存为1GB，写出一个算法：求出这个文件里的整数里不包含的一个整数答:方法一: 4个字节表示的整数，总共只有2^32约等于4G个可能。 
为了简单起见，可以假设都是无符号整数。 
分配500MB内存，每一bit代表一个整数，刚好可以表示完4个字节的整数，初始值为0。基本思想每读入一个数，就把它对应的bit位置为１，处理完40G个数后，对500M的内存遍历，找出一个bit为0的位，输出对应的整数就是未出现的。 
算法流程： 
１）分配５００ＭＢ内存buf，初始化为０ 
２）unsigned int x=0x1; 
    for each int j in file 
    buf=buf |x < <j; 
    end 
(3) for(unsigned int i=0; i <= 0xffffffff; i++) 
        if (!(buf & x < <i)) 
        { 
            output(i); 
            break; 
        } 
以上只是针对无符号的，有符号的整数可以依此类推。方法二:文件可以分段读啊，这个是O（2n）算法，应该是很快的了，而且空间也允许的。 
不过还可以构造更快的方法的，更快的方法主要是针对定位输出的整数优化算法。 
思路大概是这样的，把值空间等分成若干个值段，比如值为无符号数，则 
00000000H-00000FFFH 
00001000H-00001FFFH 
...... 
0000F000H-0000FFFFH 
..... 
FFFFF000H-FFFFFFFFH 
这样可以订立一个规则，在一个值段范围内的数第一次出现时，对应值段指示值Xn=Xn+1，如果该值段的所有整数都出现过，则Xn=1000H，这样后面输出定位时就可以直接跳过这个值段了，因为题目仅仅要求输出一个，这样可以大大减少后面对标志数值的遍历步骤。 
理论上值段的划分有一定的算法可以快速的实现，比如利用位运算直接定位值段对应值进行计算。腾讯面试题:有1到10w这10w个数，去除2个并打乱次序，如何找出那两个数。（不准用位图！！）位图解决:位图的方法如下 
假设待处理数组为A[10w-2] 
定义一个数组B[10w],这里假设B中每个元素占用1比特,并初始化为全0 
for(i=0;i <10w-2;i++) 
{ 
B[ A[i] ]=1 
} 
那么B中不为零的元素即为缺少的数据 
这种方法的效率非常高，是计算机中最常用的算法之一其它方法:    求和以及平方和可以得到结果，不过可能求平方和运算量比较大（用64位int不会溢出）腾讯面试题:腾讯服务器每秒有2w个QQ号同时上线，找出5min内重新登入的qq号并打印出来。解答: 第二题如果空间足够大,可以定义一个大的数组 
a[qq号],初始为零,然后这个qq号登陆了就a[qq号]++ 
最后统计大于等于2的QQ号 
这个用空间来代替时间第二个题目，有不成熟的想法。 
2w x 300s 
所以用 6,000,000 个桶。删除超时的算法后面说，所以平均桶的大小是 1 。 
假设 qq 号码一共有 10^10 个，所以每个桶装的 q 号码是 10^10 / (6 * 10^6) 个，这个是插入时候的最坏效率（插入同一个桶的时候是顺序查找插入位置的）。 
qq的节点结构和上面大家讨论的基本一样，增加一个指针指向输出列表，后面说。 
struct QQstruct { 
   num_type    qqnum; 
   timestamp   last_logon_time; 
   QQstruct    *pre; 
   QQstruct    *next; 
   OutPutList *out;     // 用于 free 节点的时候，顺便更新一下输出列表。 
} 

另外增加两个指针列表。 
第一个大小 300 的循环链表，自带一个指向 QQStruct 的域，循环存 300 秒内的qq指针。时间一过 
就 free 掉， 所以保证所有桶占用的空间在 2w X 300 以内。 
第二个是 输出列表， 就是存放题目需要输出的节点。 
如果登陆的用户，5分钟内完全没有重复的话，每秒 free 掉 2w 个节点。 
不过在 free 的时候，要判断一下时间是不是真的超时，因为把节点入桶的时候，遇到重复的，会更 
新一下最后登陆的时间。当然啦，这个时候，要把这个 qq 号码放到需要输出的列表里面