Posted on 2007-04-26 12:37
ZelluX 閱讀(4535)
評論(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[] 是不重復的話可以的，
: : 如果在中位數附近重復的比較厲害的話，呵呵