腾讯笔试题解

作者: Peak Wong, 　出处:IT专家网,　责任编辑: 李书琴,　

2007-11-21 17:36

【IT专家网独家】问题：在一个文件中有 10G 个整数，乱序排列，要求找出中位数。内存限制为 2G。只写出思路即可。

　　Peak Wong：

　　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段，可以分的段数少一些，这样在扫描记数段时会快一些，还能节省一些内存。