題目：100億個整數(shù)庐镐，求最大的1萬個數(shù)冈爹，并說出算法的時間復(fù)雜度 算法：如果把100億個數(shù)全部讀入內(nèi)存忠蝗，需要100 0000 0000 * 4B 大約40G的內(nèi)存，這顯然是不現(xiàn)實的奋构。 我們可以在內(nèi)存中維護(hù)一個大小為10000的最小堆拱层，每次從文件讀一個數(shù)弥臼，與最小堆的堆頂元素比較，若比堆頂元素大根灯， 則替換掉堆頂元素径缅，然后調(diào)整堆。最后剩下的堆內(nèi)元素即為最大的1萬個數(shù)烙肺，算法復(fù)雜度為O(NlogN) 實現(xiàn)：從文件讀數(shù)據(jù)有講究纳猪，如果每次只讀一個數(shù)，效率太低茬高，可以維護(hù)一個輸入緩沖區(qū)兆旬，一次讀取一大塊數(shù)據(jù)到內(nèi)存， 用完了又從文件接著讀怎栽，這樣效率高很多丽猬，緩沖區(qū)的大小也有講究，一般要設(shè)為4KB的整數(shù)倍熏瞄，因為磁盤的塊大小一般 就是4KB維護(hù)一個大根堆
100億個數(shù)取出最大的10000個
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
- 文/潘曉璐 我一進(jì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)化后凌停，收錄于我的新書《編程之法》第六章中，新書...
- 從三月份找實習(xí)到現(xiàn)在售滤，面了一些公司罚拟，掛了不少，但最終還是拿到小米完箩、百度赐俗、阿里、京東弊知、新浪阻逮、CVTE、樂視家的研發(fā)崗...
- 前兩天面試3面學(xué)長問我的這個問題（想說TEG的3個面試學(xué)長都是好和藹秩彤，希望能完成最后一面叔扼，各方面原因造成我無比想去...
- 概述 我們都知道一個進(jìn)程是與其他進(jìn)程共享CPU和內(nèi)存資源的。正因如此漫雷，操作系統(tǒng)需要有一套完善的內(nèi)存管理機制才能防止...
- 一瓜富、溫故而知新 1. 內(nèi)存不夠怎么辦 內(nèi)存簡單分配策略的問題地址空間不隔離內(nèi)存使用效率低程序運行的地址不確定 關(guān)于...
