[程式員面試題精選100題]5.查找最小的k個元素

輸入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中的資料容器。

參考：   堆排序

程式設計之美之尋找最大的k個數