使用堆的時間複雜度為O(n log k)（n為元素個數，k為取前多少個數），而使用Quickselect的平均時間複雜度為O(n)，優於使用堆的演算法，而且顯然已經是理論下限。 @D Flip Flop 是這題下第一個提出這一正確思路的（看不懂或不想看上面的英文維基百科連結的話，我簡單搜了一下找到一篇中文介紹選取第K大數的快速選擇演算法和注意事項 | Comzyh的部落格）如果非得擔心naive實現中的O(n^2)最壞時間複雜度，我們有Median of medians可以以最壞時間複雜度O(n)求出中位數，在Quickselect中總是以中位數作為主元（pivot）即可保證最壞時間複雜度仍為O(n)。當然，這樣做會帶來非常大的常數懲罰，因此只有漸近分析上的意義，實踐中無意義。（中文介紹十四、第三章再續：快速選擇SELECT演算法的深入分析與實現 - Hibernate4 - 部落格園，這篇包含了普通的Quickselect）本題要求的20億個數，每個32位的話總共大約7.5G，每個64位的話大約15G，當代（2016年12月）的伺服器單機記憶體一般都放得下。如果考慮記憶體放不下的情況，可以將檔案分成數塊（數量記為m）保證每一塊都能放進記憶體，依次處理每一個塊，用上述演算法求出每塊的前k個數並存在記憶體裡，然後將這m份“前k個數”合併成一個數組，再用上述演算法求出這mk個數中的其前k個數即可

==============================================

考的是mapreduce 大規模資料處理

不要拿著簡單的排序思路在思考，也不是需要極為準確的結果。百度 阿里大資料今年電話面試都有這個問題

我沒學過Java，但是大體的思想應該是先排序記錄重複個數，這個可以考慮用陣列實現，陣列的下標是具體數值，陣列的值是重複個數，然後再選出前一百

存資料庫的，用其他工具的都會被pass，因為這樣的工程師只是程式碼搬運工，根本不會演算法最佳化。

非常簡單的一道演算法，建立一個200堆疊，遍歷樣本取數，堆裡比取數大的全出棧，如來取數最終與某棧元素相等，全出棧元素全入棧，否則取數入棧，堆外元素入棧，堆疊滿原堆頂外丟棄。迴圈直到樣本遍歷結束。

以上演算法是取不重複的，可重複就改一行，略。

多路歸併排序。。。。....,......................................

既然是java題，這就是經典的topk問題。先取前100個數，建立一個最小堆，剩下的數依次從堆頂插入元素，同時調整堆。最後堆中的100個元素即為結果。空間複雜度為k，時間複雜度為nlogk

建立一個100個數據的MinPQ，逐個讀取資料，只要比最上面大的就刪掉最上面的，然後插入這個資料。時間nlog100。空間c，c=101

首先你要知道考題的用意在哪？這道題無非是考察你是否有最佳化演算法的思維，追求極致效能的主觀意願。之後就要先分析一下，效能瓶頸在哪裡？第一個就是大資料計算。第二是資料量足夠大，會撐爆記憶體。第三都是文字排序，還要考慮I/O瓶頸。張嘴就說取前100，然後再比較排除的人，立馬考官就會撇嘴。要我，我就先跟他噴幾個詞：用多核心，GPU加速，超執行緒，甚至是異構計算框架。先考慮加速問題！然後再說把20億的資料分塊分桶，平行計算。你都不用具體贅述後面的演算法細節了，考官就會問下一題了。

其實資料怎麼讀並不是這題目的關鍵，主要是演算法，可以先取前一百個數字先排序好在一個數組裡，然後後面數字由陣列最小元素比起進行排序，這樣複雜度肯定遠小於O(n)

傻呀，切割成N份，對每一份做快排，取每一份的前100個數字。按照這個思路不停的組合，一般三次就可以了，不管你要排100億還是200億，就這個思路。

quick(array,k)

random a in array

for(n=0→a,m=array.length→a)

if(array[n]>array[a] && array[m] <array[a])

swap(array[n],array[m])

if(a<k)return array[0→a] + quick(array[a→end,k-a)

else if(a==k)return array[0→a]

else return quick(array[0→a],k)

手機打字真尼瑪累，湊合看吧，還需要處理a的交換問題

我說個另類的解決方案，入門程式設計師就能寫好。一般實際工作中遇到也應該這樣做。

1、用語言把所有文字數字轉義為數字，然後存入資料庫。

2、建立索引。

3、select 出top100，desc。

over！何必苦苦在那裡寫自己都搞不好的演算法呢？！

這是考演算法還是考解決方案？考演算法大可不必2億這麼多，考解決方案的話最便宜的用hadoop簡簡單單就搞定了，原理是把2億資料分佈到多臺機器，每臺對本機的資料做top100排序，完了以後再把初次排序的結果重新分組，再次分佈到各臺機器上top100排序，如此迴圈而已

前面有說放資料庫的、群演算法排序的、直接大資料等，如果真是這麼簡單就皆大歡喜了！

看題面20億的數字絕對不會是直接放到記憶體中吧，應該是固化在硬碟吧。最理想的狀態應該是分散在叢集中，但是我想題目的附加條件應該是單機提取20億數字的top100。

轉換成位運算！

對檔案一次迴圈即可，讀入一百條資料，排序並找出最大值，依次讀入資料，如果小於最大值，則更新列表與最大值，迴圈至完。複雜度：檔案讀一次即O(n)，記憶體排序組最大O(n)*100次。有實踐過更好請劈我。

這個題簡單到死吧…建立一個100個元素的A陣列…取100字串作為初始值…之後排序…取一個新值和陣列最後一個比較替換再排序…如此20億次即可……最佳化一下就是用新值倒數查詢…找到比新值大的位置…後面全更新為新元素…再排序…如此反覆……100元素排序很快的…並且除了第一次之後排序的代價極低…基本運算時間就是 資料量總大小除以硬碟速度…

明顯是考你有無大資料處理的思維啊，一上來就記憶體排序演算法，能排嗎，記憶體才多大，20億的數字文字就算一個數字一個位元組，也上G了啊，我的方法是，首先掃描20億的檔案，對每個數字做如下處理：每個數字字串轉換為數字(一個數字32位算)，從左邊第一位開始，是1的放在A1檔案上，為0的放在A2檔案上，這樣經歷一次掃描後分為兩個檔案，A1裡的數字肯定比A2大，第二次掃描A1檔案，同理將每個數字的第二位為1的放在B1檔案裡，為0的放在B2檔案裡，依此類推(當然可能存在沒資料的檔案，那此時就拿第二個檔案作為下一組檔案的基礎)，拆分到適合記憶體處理的量後，才能使用記憶體排序……

20億數字，按一個數4位元組，也就10G不到，現在一般的桌上型電腦都有那麼大記憶體，更別提伺服器了。最快麼就桶排序，20億長度的陣列，遍歷一次，結果就出來了，其實還可以對資料做初步評估，比如20億個數，前100，估計落在1-100000之間機率99.9%，那消耗就更小了

首先，任何說資料庫的，Hadoop的，都會直接pass，考你演算法，所答非所問。其次直接記憶體排序的，題目是資料文字，沒有說明數字長度，可能常見的32或者64位都不夠，大數乘法又不是沒做過。高io的排序，理想的方式是儘量多且儘快的排除資料。個人的想法是這樣，首先對考慮正負號與小數點，將數字按照整數長度進行分桶。正常情況下，只需要對某幾個桶進行操作了，其他資料可以忽略。最壞情況下，所有數字都在一個桶裡。其次，對需要排序的桶，採用桶排序，從最高位開始，由高到底。最終給出結果。複雜度最好是o(n)，最差是o(mn)，m是數字最大長度。正常應該是o(nlogm)，和快排差不多，只是高io

如果用SQL就簡單多了，把數字轉為表，放在columnlist列，然後執行

select

Top 100

Columnlist

Frome table name

Oder by columnlist Desc