posts - 403, comments - 310, trackbacks - 0, articles - 7
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

水源上看到的腾讯笔试题

Posted on 2007-04-26 12:37 ZelluX 阅读(4455) 评论(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[] 是不重复的话可以的,
: : 如果在中位数附近重复的比较厉害的话,呵呵


评论

# re: 水源上看到的腾讯笔试题  回复  更多评论   

2008-07-15 16:45 by 不说
恩。想法不错啊

# re: 水源上看到的腾讯笔试题  回复  更多评论   

2008-07-15 16:46 by 不说
但是内存利用率不高貌似

# re: 水源上看到的腾讯笔试题  回复  更多评论   

2009-05-30 22:23 by leesa
恩 这个方法赞啊

只有注册用户登录后才能发表评论。


网站导航: