【出自BD面试题】
难度系数：★★★★☆ 被考察系数：★★★★☆
题目描述：
从5亿个数中找出中位数。数据排序后，位置在最中间的数值就是中位数。当样本数为奇数时，中位数=（N+1）/2；当样本数为偶数时，中位数为N/2与1+N/2的均值（那么10G个数的中位数，就是第5G大的数与第5G+1大的数的平均值了）。
分析与解答：
如果这道题目没有内存大小的限制，可以把所有的数字排序后找出中位数，但是最好的排序算法的时间复杂度都是O（NlogN）（N为数字的个数）。这里介绍另外一种求解中位数的算法：双堆法。
方法一：双堆法
这种方法的主要思路是维护两个堆，一个大顶堆，一个小顶堆，且这两个堆需要满足如下两个特性：
特性一：大顶堆中最大的数值小于等于小顶堆中最小的数。
特性二：保证这两个堆中的元素个数的差不能超过1。
当数据总数为偶数的时候，当这两个堆建立好以后，中位数显然就是两个堆顶元素的平均值。当数据总数为奇数的时候，根据两个堆的大小，中位数一定在数据多的堆的堆顶。对于本题而言，具体实现思路：维护两个堆maxHeap与minHeap，这两个堆的大小分别为max_size和min_size。然后开始遍历数字。对于遍历到的数字data：
（1）如果data＜maxHeap的堆顶元素，此时为了满足特性1，只能把data插入到maxHeap中。为了满足特性二，需要分以下几种情况讨论。
a）如果max_size＜=min_size，说明大顶堆元素个数小于小顶堆元素个数，此时把data直接插入大顶堆中，并把这个堆调整为大顶堆。
b）如果max_size＞min_size，为了保持两个堆元素个数的差不超过1，此时需要把maxHeap堆顶的元素移动到minHeap中，接着把data插入到maxHeap中。同时通过对堆的调整分别让两个堆保持大顶堆与小顶堆的特性。
（2）如果maxHeap堆顶元素＜=data＜=minHeap堆顶元素，为了满足特性一，此时可以把data插入任意一个堆中，为了满足特性二，需要分以下几种情况讨论：(www.xing528.com)
a）如果max_size＜min_size，显然需要把data插入到maxHeap中。
b）如果max_size＞min_size，显然需要把data插入到minHeap中。
c）如果max_size==min_size，可以把data插入到任意一个堆中。
（3）如果data＞maxHeap的堆顶元素，此时为了满足特性一，只能把data插入到minHeap中。为了满足特性二，需要分以下几种情况讨论。
a）如果max_size＞=min_size，那么把data插入到minHeap中。
b）如果max_size＜min_size，那么需要把minHeap堆顶元素移到maxHeap中，然后把data插入到minHeap中。
通过上述方法可以把5亿个数构建两个堆，两个堆顶元素的平均值就是中位数。
这种方法由于需要把所有的数据都加载到内存中，当数据量很大的时候，由于无法把数据一次性加载到内存中，因此这种方法比较适用于数据量小的情况。对于本题而言，5亿个数字，每个数字在内存中占4B，5亿个数字需要的内存空间为2GB内存。如果可用的内存不足2G的时候显然不能使用这种方法，因此下面介绍另外一种方法。
方法二：分治法
分治法的核心思想为把一个大的问题逐渐转换为规模较小的问题来求解。对于本题而言，顺序读取这5亿个数字；
（1）对于读取到的数字num，如果它对应的二进制中最高位为1则把这个数字写入到f1中，如果最高位是0则写入到f0中。通过这一步就可以把这5亿个数字划分成两部分，而且f0中的数字都大于f1中的数字（因为最高位是符号位）。
（2）通过上面的划分可以非常容易地知道中位数是在f0中还是在f1中，假设f1中有1亿个数，那么中位数一定在文件f0中从小到大是第1.5亿个数与它后面的一个数求平均值。
（3）对于f0可以用次高位的二进制的值继续把这个文件一分为二，使用同样的思路可以确定中位数是哪个文件中的第几个数。直到划分后的文件可以被加载到内存的时候，把数据加载到内存中后排序，从而找出中位数。
需要注意的是，这里有一种特殊情况需要考虑，当数据总数为偶数的时候，如果把文件一分为二后，发现两个文件中的数据有相同的个数，那么中位数就是数据总数小的文件中的最大值与数据总数大的文件中的最小值的平均值。对于求一个文件中所有数据的最大值或最小值，可以使用前面介绍的分治法进行求解。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
