大数的中位数问题
其实很多面试都会提到,一堆大数,我要找到其中位数,在O(N)的算法复杂度内。往往这些大数都是不能一次性读到内存中的。 腾讯面试题:10G 个整数,乱序排列,要求找出中位数。内存限制为 2G。 主要的思想就是分段去读取,其实和桶排序有些相似 首先假设是32位无符号整数。 总结: 1.以上方法只要读两遍整数,对每个整数也只是常数时间的操作,总体来说是线性时间。 2. 考虑其他情况。 若是有符号的整数,只需改变 映射即可。若是64为整数,则增加每个区段的范围,那么在第二次读数时,要考虑更多的计数。若过某个计数溢出,那么可认定所在的区段或代表整数为所求,这 里只需做好相应的处理。噢,忘了还要找第5G+1大的数了,相信有了以上的成果,找到这个数也不难了吧。 3. 时空权衡。 花费256个区段也许只是恰好配合2GB的内存(其实也不是,呵呵)。可以增大区段范围,减少区段数目,节省一些内存,虽然增加第二部分的对单个数值的计数,但第一部分对每个区段的计数加快了(总体改变??待测)。 4. 映射时尽量用位操作,由于每个区段的起点都是2的整数幂,映射起来也很方便。 答案: 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段,可以分的段数少一写,这样在扫描记数段时会快一些,还能节省一些内存) (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |