2015年数据库招聘笔试题

更新时间：2024-06-21 14:36:54 读后感我要投稿

　　在一个文件中有 10G 个整数(32位无符号数)，乱序排列，要求找出中位数。内存限制为 2G。只写出思路即可。

　　解答：

　　解题思想：类似于桶排序的思想，将32位无符号数分段如每16个一段，0-15为第1段，16-31为第2段等等，然后统计各段的数字的个数，然后就可以找到中位数所在的段了，然后就再扫描一遍(只要读入处于中位数所在的段即可)原数集即可得到中位数。(当然也有中特殊的情况就是：中位数所在的'段的整数的个数大于2G的内存，即内存还装不下该段，此时需要做细化处理：即再将该段细分，比如说将该段分为8小段，然后再找中位数所在的段)。

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

【2015年数据库招聘笔试题】相关文章：

2017年营养学专业就业前景2024-06-20