加载中…
个人资料
伊人何处
伊人何处
  • 博客等级:
  • 博客积分:0
  • 博客访问:27,154
  • 关注人气:7
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

腾讯笔试题:大数据量寻找中位数

(2007-04-24 18:46:11)
分类: 算法&逻辑
题目如下:
只有2G内存的pc机,在一个存有10G个整数的文件,从中找到中位数,写一个算法。
 
算法:
1.利用外排序的方法,进行排序 ,然后再去找中位数
 
2.另外还有个思路利用堆
先求第1G大,然后利用该元素求第2G大,然后利用第2G大,求第3G大...当然这样的话虽不需排序,但是磁盘操作会比较多,具体还需要分析下与外排序的效率哪个的磁盘IO会比较多
建立一个1g个整数的最大值堆,如果元素小于最大值则入堆,这样可以得到第1g大的那个元素然后利用这个元素,重新建一次堆,这次入堆的条件还要加上大于这个第1g大的元素,这样建完堆可以得到第2g大的那个 ...
 
3.借鉴基数排序思想
偶认为可以用位来判断计数,从最高位到最低位,为了方便表述我们假设为无符号整数,即0x00000000~0xFFFFFFFF依次递增,那么可以遍历所有数据,并记录最高位为0和1的个数(最高位为0的肯定是小于最高位为1的)记为N0、N1
那么根据N0和N1的大小就可以知道中位数的最高位是0还是1
假设N0>N1,那么再计算N00和N01,
如果N00>(N01+N1),则说明中位数的最高两位是00
再计算N000和N001.。。。依次计算就能找到中位数
 
如果改进一下,设定多个计数器
好像一次磁盘io也可以统计出N0,N00,....的数值
 
4.借鉴桶排序思想
一个整数假设是32位无符号数
第一次扫描把0~2^32-1分成2^16个区间,记录每个区间的整数数目
找出中位数具体所在区间65536*i~65536*(i+1)-1
第二次扫描则可找出具体中位数数值

第一次扫描已经找出中位数具体所在区间65536*i~65536*(i+1)-1
然后第二次扫描再统计在该区间内每个数出现的次数,就可以了


0

阅读 评论 收藏 转载 喜欢 打印举报/Report
前一篇:关于汇编
后一篇:过桥问题
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

    < 前一篇关于汇编
    后一篇 >过桥问题
      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有