Posted on 2007-04-26 12:37
ZelluX 閱讀(4538)
評(píng)論(3) 編輯 收藏 所屬分類(lèi):
Algorithm
發(fā)信人: anchorzhao (anchor), 信區(qū): Algorithm
標(biāo) 題: 請(qǐng)教騰訊筆試題
發(fā)信站: 飲水思源 (2007年04月23日13:01:40 星期一)
只有2G內(nèi)存的pc機(jī)，在一個(gè)存有10G個(gè)整數(shù)的文件，從中找到中位數(shù)，寫(xiě)一個(gè)算法。
--
※ 來(lái)源:·飲水思源 bbs.sjtu.edu.cn·[FROM: 202.120.37.193]
發(fā)信人: xreborner (xreborner), 信區(qū): Algorithm
標(biāo) 題: Re: 請(qǐng)教騰訊筆試題
發(fā)信站: 飲水思源 (2007年04月24日11:23:07 星期二), 轉(zhuǎn)信
……
一個(gè)整數(shù)假設(shè)是32位無(wú)符號(hào)數(shù)
第一次掃描把0~2^32-1分成2^16個(gè)區(qū)間，記錄每個(gè)區(qū)間的整數(shù)數(shù)目
找出中位數(shù)具體所在區(qū)間65536*i~65536*(i+1)-1
第二次掃描則可找出具體中位數(shù)數(shù)值
【 在 howe (無(wú)痕) 的大作中提到: 】
: 這小子吹牛
: 【 在 acmboy (雪狼,想創(chuàng)業(yè)，人不霸王枉少年) 的大作中提到: 】
: : 這小子夠壞的，居然不說(shuō)怎么做~~~
--
心碼合一，心中有代碼，碼中存我心；維碼無(wú)心，心動(dòng)即碼動(dòng)，代碼表我心；
維心無(wú)碼，視萬(wàn)物皆空，知萬(wàn)千變化；無(wú)碼無(wú)心，行如若無(wú)規(guī)，動(dòng)全依所意。
※ 來(lái)源:·飲水思源 bbs.sjtu.edu.cn·[FROM: 202.120.224.18]
發(fā)信人: xreborner (xreborner), 信區(qū): Algorithm
標(biāo) 題: Re: 請(qǐng)教騰訊筆試題
發(fā)信站: 飲水思源 (2007年04月24日18:37:01 星期二), 轉(zhuǎn)信
可以保證的
因?yàn)榈谝淮螔呙枰呀?jīng)找出中位數(shù)具體所在區(qū)間65536*i~65536*(i+1)-1
然后第二次掃描再統(tǒng)計(jì)在該區(qū)間內(nèi)每個(gè)數(shù)出現(xiàn)的次數(shù)
就可以了
實(shí)在是太簡(jiǎn)單了
【 在 acmboy (雪狼,想創(chuàng)業(yè)，人不霸王枉少年) 的大作中提到: 】
: anyway,good solution ，雖然不能保證兩次完成
: 【 在 acmboy (雪狼,想創(chuàng)業(yè)，人不霸王枉少年) 的大作中提到: 】
: : 如果int[] 是不重復(fù)的話(huà)可以的，
: : 如果在中位數(shù)附近重復(fù)的比較厲害的話(huà)，呵呵