腾讯的一道面试题:(与百度相似,可惜昨天百度死在这方面了)////
在一个文件中有 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段，可以分的段数少一写，这样在扫描记数段时会快一些，还能节省一些内存)

请在邮件中注明：信息来自有我网（www.unus.cn）