1樓：
1、原始資料先排序
這是最直接的思路，排序的話，有冒泡，歸併，快排，堆排，基數排序等方法，最快的是基數排序，時間複雜度O(n)，冒泡時間複雜度過高，捨棄。若資料滿足基數排序要求，一定要用基數排序。
根據記憶體是否足夠，會有內部排序和外部排序兩種方式，原理是一樣的，無非外部排序因為要頻繁讀寫磁碟因此速度會慢一些。
如果能夠內部排序，建議使用這個方法
2、淘汰法
最簡單的想法，先建立乙個10萬大小的陣列，從原始資料讀出頭10萬個資料進入陣列，對此陣列使用nlog（n）的演算法（如快排等）進行排序，之後逐個讀入原始資料的後續資料，在10萬的陣列中用二分法進行查詢，保證陣列中的資料一定是以讀出的資料中的最大的10萬個。
這個方法的時間複雜度和快排等是差不多的，但避免了全資料的排序（因為你不知道記憶體夠不夠，全排序有可能使用到外部排序）
3、分治法
資料分為n份，每份找到前10萬個，再針對n個10萬找到前面的10萬個
最後注意一下，資料中的資料應該會有重複的，針對重複的資料要進行處理哈。
2樓：V1990
先切成若K塊，每塊先做內部排序然後存起來，再K路歸併，放到乙個最大堆裡面，出來的前10萬個數就是最大的10萬個數了。
這K塊是可以進行平行計算的
3樓：安靜地吹牛
此類問題一般用sqlite/oracle，設計表，開事務，把資料插入資料庫，然後做選擇排序，去拉屎抽菸王者榮耀知乎，總之過陣子回來就解決了。
面試官要囉嗦就說，資料處理，密集cpu操作用你妹的php。
4樓：old tab
m取前n
以取小為例吧。我喜歡小。
以資料總量，分：小、中、大，三種情況來分析。
1、小：全部讀入記憶體，排序，取前n。
2、中：
2.1：分幾次讀入（次數為k=總資料/記憶體大小），分別排序、寫回讀入點。致全部讀一遍。形成k個順串（稱之資料錐）。
2.2：各錐讀取一節(量為記憶體/K)，到記憶體（稱之：錐節）。
2.2：各錐節尖做比較，小的寫到另一塊記憶體區（稱之輸出緩區）。如，某錐緩節空，讀該錐的下一節。
2.3：致輸出快取區滿。
2.4：寫到結果檔案。
2.5：結果夠，結束。否則，繼續2.2。
3、大：
3.1：若干單機，做2.1到2.3，暫停。
3.2：另一單機，做總機。從各單機輸出快取區，讀一節到總機記憶體區（稱總錐節）。
3.3：各總錐節尖做比較，小的寫到總機的另一塊記憶體區（稱之總輸出快取區）。如，某總錐節空，讀該錐對應單機輸出快取的下一節。
3.4：總快取區滿，寫到結果檔案。
3.5：結果夠，結束。否則，繼續3.3。
對於資料量大的情形。做順串是免不了的。
以上演算法，結果夠時，會提前結束。
而錐節，總歸比較小。因此，可能用不著 @皆傳 的中獎法。
雖然中獎法很好玩。
5樓：鄧毅
問題是在 N 個數中，找到前 k 個數。
1億 = 100M 相對於現在的硬體來說是個很小的數，基本上可以都 fit 進記憶體。記憶體中找前 k 個數可以用 Quickselect 演算法，乙個類似 quicksort 的演算法，平均複雜度是 O(N)。
如果總資料量更多，或者可用記憶體更小，可以把所有的數分成記憶體可以放下的多個部分，每個部分分別找前 k 個，最後把所有的數放在一起再找一次前 k，如果還放不下繼續分堆。這個策略還可以讓演算法可以並行執行，有計算資源的時候降低整體執行時間。
這個演算法比建乙個大小為 k 的最大堆要快，因為後者最後得到的 k 個數是部分有序的，複雜度會變成 O(N log k)，而前者得到的前 k 個數是完全無序的。
6樓：超越
題主學過資料結構否?有個叫最小堆的東西。
記憶體有限，可以把1億個資料放在磁碟上，此外，在記憶體開闢乙個可以容納10萬個資料的最小堆。
每次從磁碟上讀取乙個資料，若最小堆未滿，則直接放入最小堆中，調整堆使其符合最小堆的性質；若最小堆已滿，則將這個數與最小堆根結點上的數值進行比較，若比根結點的數值大，則替換掉根結點上的值，然後重新調整最小堆使其符合最小堆的性質。
遍歷完1億個資料後，這個容量為10萬的最小堆裡面存放的就是前10萬個最大值了。
7樓：
先遍歷，然後分堆，比如0-999999為一堆，100000-199999為二堆，
即n堆的範圍是（n-1）*100000到n*100000-1分好後，從最大的堆往前取，直到湊夠，
比如，如果第乙個堆的數量在10W個以上，那麼可以繼續分堆，可以繼續分堆，縮小範圍，也可以用排除法，比如最大的堆的數量在110000.則取這堆最小的10000，排除即可。
如果10W個數分布在幾個堆裡，那麼必然存在前幾個堆全取，最後乙個堆取部分，最後的臨界堆，這時可以繼續分堆，也可以用雙向迴圈鍊錶取少量的top N.
當然也可以用乙個10W節點的雙向迴圈鍊錶，插入去尾。
時間複雜度是 n log n * m
其中，n=100000,m是陣列長度，
構建二叉樹要好一些，不過，當場寫不出二叉樹了，所以就沒採取二叉樹。
8樓：皆傳
好好回答一下吧。
首先對於1億的資料量，要求不高的話，大可只使用乙個最小堆來維護前10萬個最大的數。
不妨設數的總數為N，需要選出的數為M，那麼這種方法帶來的時間複雜度為：
這個方法最大的缺點是沒有平行計算。
如果比1億資料量再大，比如到100億這個量級，那麼就需要使用平行計算了，下面我詳細說一下我的思路。
1) 首先將這些資料隨機分成K堆，不妨假設正好平均分配，時間複雜度為。
2) 使用K個任務並行的選出每一堆的前M大的數，這一步的時間複雜度為，此時生成了K組長度為M的有序序列。
3) 使用多路歸併排序選出這K組序列的前M大的數，這一步的時間複雜度為
因此假設第2步並行完成，那麼總體的時間複雜度就是。至此演算法得到了常數級別的優化。
但是還沒完，注意到2)中每個序列都選了前M大的數，這個是可以繼續改進的。
我們可以想象一種場景：2個桶裡總共有10個球，球是隨機分布的，規定一種操作可以從這2個桶裡拿至多L個球，這時我們怎麼確定這個L使得我們能夠以乙個我們能接受的概率拿到所有的球？
顯然當L=10的時候，我們當然可以100%的拿到這全部球，但是開銷太大了。由於球是隨機分布的，可以知道10個球全部落入落入乙個盒子裡的概率非常的小，是。因此我們可以先把這種請當當成乙個中彩票的事件，先不管他，直接把L設成9。
既然我們犧牲了一部分可靠性降低了開銷，那麼為什麼不能把L設的在低一點？究竟應該設多低？
這其實是另外的乙個問題了，我認為為了解決這個問題不應該從L入手，而是我們設定乙個最低能接受的可靠性概率P，找到最小的L滿足我們要求的P即可。
因此我們可以使用如上方法優化2)。設我們要求的最低可靠性為P, 優化函式為
2) 使用K個任務並行的選出每一堆的前大的數，這一步的時間複雜度為, 此時生成了K組長度為的有序序列。
我可以給出乙個數, 可以看出這個函式的威力。所以用這種方法，可以在實際中獲得很多倍的速度提公升。
但是必須解決的問題是可靠性問題，但這個問題其實很好辦，只需要驗證一下在3)時有沒有把乙個序列用盡，如果用盡了並且最後乙個數不是這個序列裡的最後乙個數，那麼說明這個序列的第個數也可能出現在最壞的結果。那麼最簡單的做法就是再從這個序列中補上一部分資料，使得最後的答案時正確的。
所以這時我們得到了乙個以P為成功率的演算法，這個演算法可能比未優化前快好多倍，但是有(1-P)的中獎概率。欣慰的是我們可以判斷中沒中獎，再不濟就是拋棄這次的結果再跑一次未優化前的演算法唄。
9樓：黎晨
很久沒有碰資料結構了，只能說下思維框架。
1.先遍歷前10萬個數字，放到乙個有序資料結構中，並且記錄下這組數的最小值B；
2.遍歷後面1億-10萬個數字，取出乙個數字A，和有序結構中的最小值B進行比較，如果大於最小值B，則A進入有序陣列，最小值B退出有序陣列；
3.重新計算有序陣列的最小值B；
4.重複這個過程直到結束。
遍歷1億個數字是無法縮短時間的，那麼程式的效能就在於如何在10萬個數字盡快找到最小值了。
這個是二叉樹最擅長的問題，你在遍歷的同時也已經完成了二叉樹的排序和插入工作。
不好意思的是，我已經基本忘記二叉樹怎麼寫了。o_o||
如何評價大資料的未來？
406龔煽使 何為資源化，是指大資料成為企業和社會關注的重要戰略資源，並已成為大家爭相搶奪的新焦點。因而，企業必須要提前制定大資料營銷戰略計畫，搶占市場先機。大資料離不開雲處理，雲處理為大資料提供了彈性可拓寬的基礎裝置，是產生大資料的平台之一。自2013年開始，大資料技術已開始和雲計算技術緊密結合，...
大資料資料倉儲的發展和如何延伸？
CodingMan 目前大資料底層以hive建立資料倉儲，可用spark 進行一些ETL相關的事情，另外對於OLAP的分析可以使用Kylin或者Druid，不過首先這些技術的運用要看具體的使用場景 Duke Yu 這個問題好飄飄！方向很多很多！簡單的說資料分析類的東西大概有3個方向，OLAP就是各個...
如何看待大資料網路的出現
北遠方 我就問在座的各位，買到的商品滿不滿意，到底價效比高不高，有沒有帶來方便。然後賺不賺錢再去問必勝，至於工廠賺多賺少，只有工廠老闆知道，咱們的猜測只是猜測，還有裡面的私人訂製，小的定製是要加錢的 不是像一樓那樣說的我很看好必要！ Nameless1970 其實就是廠家直銷庫存,尼康手機是C2M之...