Posted on 2007-04-26 12:37
ZelluX 阅读(4530)
评论(3) 编辑 收藏 所属分类:
Algorithm
发信人: anchorzhao (anchor), 信区: Algorithm
标 题: 请教腾讯笔试题
发信站: 饮水思源 (2007年04月23日13:01:40 星期一)
只有2G内存的pc机，在一个存有10G个整数的文件，从中找到中位数，写一个算法。
--
※ 来源:·饮水思源 bbs.sjtu.edu.cn·[FROM: 202.120.37.193]
发信人: xreborner (xreborner), 信区: Algorithm
标 题: Re: 请教腾讯笔试题
发信站: 饮水思源 (2007年04月24日11:23:07 星期二), 转信
……
一个整数假设是32位无符号数
第一次扫描把0~2^32-1分成2^16个区间，记录每个区间的整数数目
找出中位数具体所在区间65536*i~65536*(i+1)-1
第二次扫描则可找出具体中位数数值
【 在 howe (无痕) 的大作中提到: 】
: 这小子吹牛
: 【 在 acmboy (雪狼,想创业，人不霸王枉少年) 的大作中提到: 】
: : 这小子够坏的，居然不说怎么做~~~
--
心码合一，心中有代码，码中存我心；维码无心，心动即码动，代码表我心；
维心无码，视万物皆空，知万千变化；无码无心，行如若无规，动全依所意。
※ 来源:·饮水思源 bbs.sjtu.edu.cn·[FROM: 202.120.224.18]
发信人: xreborner (xreborner), 信区: Algorithm
标 题: Re: 请教腾讯笔试题
发信站: 饮水思源 (2007年04月24日18:37:01 星期二), 转信
可以保证的
因为第一次扫描已经找出中位数具体所在区间65536*i~65536*(i+1)-1
然后第二次扫描再统计在该区间内每个数出现的次数
就可以了
实在是太简单了
【 在 acmboy (雪狼,想创业，人不霸王枉少年) 的大作中提到: 】
: anyway,good solution ，虽然不能保证两次完成
: 【 在 acmboy (雪狼,想创业，人不霸王枉少年) 的大作中提到: 】
: : 如果int[] 是不重复的话可以的，
: : 如果在中位数附近重复的比较厉害的话，呵呵