一验夯、在一個文件中有 10G 個整數(shù)，亂序排列嚷辅，要求找出中位數(shù)簿姨。內(nèi)存限制為 2G。
解決方案：桶排序簸搞。
1扁位、讀入內(nèi)存2G數(shù)據(jù)，一個整數(shù)四個字節(jié)趁俊，將這四個字節(jié)取最高的一個字節(jié)即8位（用>>位移法取出）
2域仇、一個字節(jié)共256種可能性，開辟256個文件寺擂，根據(jù)每個數(shù)的高8位寫入文件
3暇务、重復(fù)上述算法直到所有數(shù)算完泼掠，同時記錄每個文件中的數(shù)的數(shù)量。
4垦细、第一個文件數(shù)的個數(shù)+第二個文件數(shù)的個數(shù)... 可以判斷中位數(shù)在第幾個桶里面
5择镇、把這個桶整個讀入內(nèi)存，之后如果大小小于2G就不用寫文件了括改，在內(nèi)存中計算就可以
6腻豌、這個桶里面的數(shù)高8位都一樣，用1中的方法去取第二高的字節(jié)并重復(fù)上面的算法嘱能，然后取第三高的字節(jié)重復(fù)算法吝梅，最后一個字節(jié)可以接著桶排序，也可以快排惹骂，就能得出中位數(shù)了
二苏携、10億個整數(shù)，找出最大的1000個对粪。
解決方案：有重復(fù)可以用分治法+快排或者小頂堆右冻，如果沒有重復(fù)可以桶排
1、分治法+快排：將數(shù)分成內(nèi)存能裝的下的分?jǐn)?shù)衩侥，比如100份国旷，每分進行快排得到最大的1000個，然后將100*1000個數(shù)進行快排取1000個茫死。這里快排方法如下：每趟快排可以將數(shù)組分成數(shù)量不一定的兩部分跪但，如果大的那份多余1000，再對著分進行一次快排峦萎，如果再多再對多的那份快排一次屡久，如果少了則對少的這份快排一次，如此循環(huán)直到夠1000個為止爱榔。
2被环、小頂堆：先從文件中讀取1000個數(shù)到內(nèi)存，建小頂堆详幽，之后依次讀取筛欢，每讀一個數(shù)就和堆頂比較，小于堆頂則丟棄唇聘，大于堆頂則與堆頂交換再重建堆版姑，直到全部讀取完畢。
3迟郎、桶排序：按最高位分256個桶剥险，最高的一個應(yīng)該超過1000個數(shù)，再把這個桶拿出來按第二位繼續(xù)分桶宪肖，直到夠數(shù)了表制。
大數(shù)據(jù)問題處理
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
- 文/潘曉璐 我一進店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來镶骗，“玉大人桶现，你說我怎么就攤上這事《︽ⅲ” “怎么了骡和？”我有些...
- 文/不壞的土叔 我叫張陵，是天一觀的道長相寇。 經(jīng)常有香客問我慰于，道長，這世上最難降的妖魔是什么唤衫？ 我笑而不...
- 正文 為了忘掉前任婆赠，我火速辦了婚禮，結(jié)果婚禮上佳励，老公的妹妹穿的比我還像新娘休里。我一直安慰自己，他們只是感情好赃承，可當(dāng)我...
- 文/花漫 我一把揭開白布妙黍。 她就那樣靜靜地躺著，像睡著了一般瞧剖。 火紅的嫁衣襯著肌膚如雪拭嫁。 梳的紋絲不亂的頭發(fā)上，一...
- 文/蒼蘭香墨 我猛地睜開眼堵泽，長吁一口氣：“原來是場噩夢啊……” “哼修己！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起迎罗，我...
- 正文 年R本政府宣布，位于F島的核電站圃酵，受9級特大地震影響柳畔，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜郭赐，卻給世界環(huán)境...
- 文/蒙蒙 一薪韩、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧堪置，春花似錦躬存、人聲如沸。這莊子的主人今日做“春日...
- 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至坎匿，卻和暖如春盾剩，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背替蔬。 一陣腳步聲響...
推薦閱讀更多精彩內(nèi)容
- 教你如何迅速秒殺掉：99%的海量數(shù)據(jù)處理面試題 本文經(jīng)過大量細(xì)致的優(yōu)化后挤巡，收錄于我的新書《編程之法》第六章中，新書...
- 摘要：本文將向您講述諸多數(shù)據(jù)處理面試題以及方法的總結(jié)酷麦。 第一部分矿卑、十道海量數(shù)據(jù)處理面試題 1、海量日志數(shù)據(jù)沃饶，提取出...
- Android 自定義View的各種姿勢1 Activity的顯示之ViewRootImpl詳解 Activity...
- 第一部分母廷、十道海量數(shù)據(jù)處理面試題 1、海量日志數(shù)據(jù)糊肤，提取出某日訪問百度次數(shù)最多的那個IP琴昆。 此題，在我之前的一篇文...
