題目：輸入n個整數，輸出其中最小的k個。

例如輸入1，2，3，4，5，6，7和8這8個數字，則最小的4個數字為1，2，3和4。

分析：這道題最簡單的思路莫過于把輸入的n個整數排序，這樣排在最前面的k個數就是最小的k個數。只是這種思路的時間復雜度為O(nlogn)。我們試著尋找更快的解決思路。

我們可以先創建一個大小為k的數據容器來存儲最小的k個數字。接下來我們每次從輸入的n個整數中讀入一個數。如果容器中已有的數字少于k個，則直接把這次讀入的整數放入容器之中；如果容器中已有k個數字了，也就是容器已滿，此時我們不能再插入新的數字而只能替換已有的數字。我們找出這已有的k個數中最大值，然和拿這次待插入的整數和這個最大值進行比較。如果待插入的值比當前已有的最大值小，則用這個數替換替換當前已有的最大值；如果帶插入的值比當前已有的最大值還要大，那么這個數不可能是最小的k個整數之一，因為我們容器內已經有k個數字比它小了，于是我們可以拋棄這個整數。

因此當容器滿了之后，我們要做三件事情：一是在k個整數中找到最大數，二是有可能在這個容器中刪除最大數，三是可能要插入一個新的數字，并保證k個整數依然是排序的。如果我們用一個二叉樹來實現這個數據容器，那么我們能在O(logk)時間內實現這三步操作。因此對于n個輸入數字而言，總的時間效率就是O(nlogk)。

我們可以選擇用不同的二叉樹來實現這個數據容器。由于我們每次都需要找到k個整數中的最大數字，我們很容易想到用最大堆。在最大堆中，根結點的值總是大于它的子樹中任意結點的值。于是我們每次可以在O(1)得到已有的k個數字中的最大值，但需要O(logk)時間完成刪除以及插入操作。

我們自己從頭實現一個最大堆需要一定的代碼。我們還可以采用紅黑樹來實現我們的容器。紅黑樹通過把結點分為紅、黑兩種顏色并根據一些規則確保樹是平衡的，從而保證在紅黑樹中查找、刪除和插入操作都只需要O(logk)。在STL中set和multiset都是基于紅黑樹實現的。如果面試官不反對我們用STL中的數據容器，我們就直接拿過來用吧。下面是基于STL中的multiset的參考代碼：

typedef multiset<int, greater<int> > IntHeap;/// // find k least numbers in a vector /// void FindKLeastNumbers (const vector<int>& data, // a vector of dataIntHeap& leastNumbers, // k least numbers, outputunsigned int k ) {leastNumbers.clear();if(k == 0 || data.size() < k)return;vector<int>::const_iterator iter = data.begin();for(; iter != data.end(); ++ iter){// if less than k numbers was inserted into leastNumbersif((leastNumbers.size()) < k)leastNumbers.insert(*iter);// leastNumbers contains k numbers and it's full nowelse{// first number in leastNumbers is the greatest oneIntHeap::iterator iterFirst = leastNumbers.begin();// if is less than the previous greatest number if(*iter < *(leastNumbers.begin())){// replace the previous greatest numberleastNumbers.erase(iterFirst);leastNumbers.insert(*iter);}}} }

本文已經收錄到《劍指Offer——名企面試官精講典型編程題》一書中，有改動，書中的分析講解更加詳細，并且還介紹了一種O(n)的算法。歡迎關注。在我的英文版博客（

http://codercareer.blogspot.com/2011/09/no-05-least-k-numbers.html ）中也討論了這個問題，感興趣的讀者可以去看看英文的博客。
????? 本題已被 九度Online Judge系統收錄，歡迎讀者移步到 http://ac.jobdu.com/hhtproblems.php在線測試自己的代碼。

博主何海濤對本博客文章享有版權。網絡轉載請注明出處http://zhedahht.blog.163.com/。整理出版物請和作者聯系。對解題思路有任何建議，歡迎在評論中告知，或者加我微博http://weibo.com/zhedahht或者http://t.163.com/zhedahht與我討論。謝謝。

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的程序员面试题精选100题(05)－查找最小的k个元素[算法]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。