一个很大的文件，存放了10G个整数的乱序数列，如何用程序找出中位数。

一个很大的文件，存放了10G个整数的乱序数列，如何用程序找出中位数。

一、梳理审题

一、看清题目：

注意这个题目的量词，这个文件中有10G个整数，而不是这个文件占了10G的内存空间。

二、一些疑问：

在计算机中我们讲的G、M等都是存储容量的概念，但是一般都会在会面加上B，即Byte字节的意思，如1GB=1024MB，而在计算机中G默认为是GB的缩写。所以这个题目我认为出的不严谨，因为10G个，”个“字作为一个量词，前面应该是个单纯的数字，但是这里却说的是10G，存储容量？所以搞的人有些云里雾里，包括网络上的一些博客，对于这一点都是一笔带过，没有做过多的讨论或思索。

三、自己假设：

我在这里姑且揣测题目作者所认为的10G个等同于10*1024*1024*1024个，但明显题目中的这个表述是有问题的。

二、分析问题

一个文件中有10G个！个！数，一共2G内存，求中位数，10G是偶数，那也就第n/2个数和第(n+1)/2个数相加除以二。

10G=10*1024*1024*1024，1024=2^10

10G=10*2^30=5*2^31

第一步：在计算机中如何表示10G个这个数字？

因为5*2^31 > 2^32，所以要表示10G这个数量(假如文件中有10G个1)，32位是存不下的，我们要用64位进行存储。

第二步：分区间

一共有2G内存，那么一次性读入内存的数的个数是 2G / 64bit（按byte和bit去除得到的只是一个比例） = 2^31 /2^3= 2^28个，单位就是个，不是M等等，网上的很多文章中256M的表述是错的，因为M在计算机中是MB的缩写是空间单位，而在数学中M=兆=一百万。

第三步：求区间的表示范围

区间段有限，取值范围较大，一共有2^32个数（0 ~ 2^31-1），但是只有2^28个区间段（区间段可以理解为容器或者桶）则一个桶里面要容纳 2^32/2^28=2^4=16,每个区间段要放16个数。

即第一个桶放0-15的数，而16-31则放在第二个桶里面...以此类推

第四步：第一次遍历

然后我们开始遍历，将10G个数中的每一个数都放到对应的桶里面，如当前读到数字为18则放到第二个桶里面，第二个桶中所含有的数字总个数+1。遍历完，我们将10G个数中的每一个数都放在，他们应在的那个区间段（桶）里面了，这个2^28个桶是在内存中的，每个桶64位，恰好装满2G内存。

第五步：确定中位数所在的区间

那么然后，我们对于这个区间段队列中的每个段的总个数进行累加，当加到第5G个！个！数时，停止，那么第！第！5G个数所在的区间段就是中位数所在的区间段，将此区间段表示为[a,a+15]，在此区间段之前的所有区间段所包含数字的总个数为m。

释放掉内存后...

第六步：确定最终的位置

再次遍历10G个数，统计出现在[a,a+15]这个区间段中的，每个值，所出现的个数，最多有可能有16个数字，当然也有可能只有一个，按照a..a+15进行排序，设为n0,n1...n15。

当m+n0+n1...+nx 首次大于5G时，此时的 a+x 就是所求的中位数（当总数为奇数时），为偶数时则是（a+x+a+x-1）/2，当然有可能a+x和a+x-1在两个区间中。

这里有一个极端情况，就是所有10G个数都落在同一个桶里面，那么在第二次遍历的时候就需要对全部10G个数进行遍历。

参考文章：​​http://blog.sina.com-/s/blog_8e9c63c70101f5pl.html​​

作者：​​翎野君​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。