1. 有1億個浮點數，如果找出期中最大的10000個？

• 最容易想到的方法是將數據全部排序，然后在排序后的集合中進行查找，最快的排序算法的時間復雜度一般為O（nlogn），如快速排序。但是在32位的機器上，每個float類型占4個字節，1億個浮點數就要占用400MB的存儲空間，對于一些可用內存小于400M的計算機而言，很顯然是不能一次將全部數據讀入內存進行排序的。其實即使內存能夠滿足要求（我機器內存都是8GB），該方法也并不高效，因為題目的目的是尋找出最大的10000個數即可，而排序卻是將所有的元素都排序了，做了很多的無用功。

?

• 第二種方法為局部淘汰法，該方法與排序方法類似，用一個容器保存前10000個數，然后將剩余的所有數字——與容器內的最小數字相比，如果所有后續的元素都比容器內的10000個數還小，那么容器內這個10000個數就是最大10000個數。如果某一后續元素比容器內最小數字大，則刪掉容器內最小元素，并將該元素插入容器，最后遍歷完這1億個數，得到的結果容器中保存的數即為最終結果了。此時的時間復雜度為O（n+m^2），其中m為容器的大小，即10000。

?

• ?第三種方法是分治法，將1億個數據分成100份，每份100萬個數據，找到每份數據中最大的10000個，最后在剩下的100*10000個數據里面找出最大的10000個。如果100萬數據選擇足夠理想，那么可以過濾掉1億數據里面99%的數據。100萬個數據里面查找最大的10000個數據的方法如下：用快速排序的方法，將數據分為2堆，如果大的那堆個數N大于10000個，繼續對大堆快速排序一次分成2堆，如果大的那堆個數N大于10000個，繼續對大堆快速排序一次分成2堆，如果大堆個數N小于10000個，就在小的那堆里面快速排序一次，找第10000-n大的數字；遞歸以上過程，就可以找到第1w大的數。參考上面的找出第1w大數字，就可以類似的方法找到前10000大數字了。此種方法需要每次的內存空間為10^6*4=4MB，一共需要101次這樣的比較。

?

• 第四種方法是Hash法。如果這1億個數里面有很多重復的數，先通過Hash法，把這1億個數字去重復，這樣如果重復率很高的話，會減少很大的內存用量，從而縮小運算空間，然后通過分治法或最小堆法查找最大的10000個數。

?

• 第五種方法采用最小堆。首先讀入前10000個數來創建大小為10000的最小堆，建堆的時間復雜度為O（mlogm）（m為數組的大小即為10000），然后遍歷后續的數字，并于堆頂（最小）數字進行比較。如果比最小的數小，則繼續讀取后續數字；如果比堆頂數字大，則替換堆頂元素并重新調整堆為最小堆。整個過程直至1億個數全部遍歷完為止。然后按照中序遍歷的方式輸出當前堆中的所有10000個數字。該算法的時間復雜度為O（nmlogm），空間復雜度是10000（常數）。

?

參考資料：

1.?海量數據處理 - 10億個數中找出最大的10000個數（top K問題）