在一个文件中有10G个整数，乱序排序，要求找出中位数。从10G个数中找到中数在一个文件中有10G个整数，乱序排列，要求找出中位数。内存限制为2G。不妨假设10G个整数是64bit的。2G内存可

Question

在一个文件中有10G个整数，乱序排序，要求找出中位数。
从10G个数中找到中数
在一个文件中有 10G 个整数，乱序排列，要求找出中位数。内存限制为 2G。
不妨假设10G个整数是64bit的。
2G内存可以存放256M个64bit整数。
我们可以将64bit的整数空间平均分成256M个取值范围，用2G的内存对每个取值范围内出现整数个数进行统计。这样遍历一边10G整数后，我们便知道中数在那个范围内出现，以及这个范围内总共出现了多少个整数。
如果中数所在范围出现的整数比较少，我们就可以对这个范围内的整数进行排序，找到中数。如果这个范围内出现的整数比较多，我们还可以采用同样的方法将此范围再次分成多个更小的范围（256M=2^28，所以最多需要3次就可以将此范围缩小到1，也就找到了中数）。
这是腾讯的一个笔试题，想知道“将64bit的整数空间平均分成256M个取值范围”是什么意思。。求教。。

Answer 1

首先说明一点，64bite的整数足以存储10G这个数值。
然后换个思维理解，比如有20个数，数的范围是（1-10），而内存只能装入两个数。用内存里的这两个数统计范围为（0,5），（6,10）的数出现的次数，比如内存里两个数的取值是4,16，显然中位数(姑且认为是求第10位）出现在（6,10）中的第6出现的数。
这个时候，内存两个数统计范围变成（6,8），（9,10），统计这两个区间内范围出现的数的次数，如果是8,8，中位数是在（6,8）中第6次出现的数。
第三次统计，内存两个数统计的范围是（6，7），（8），如果是7,1，那么所求的中位数还是（6,7）第6次出现的数。
第四次统计，内存两个数为（6），（7），如果内存第一个数>=6,则所求数为6，否则所求数为7。
这样应该能理解了吧。