問題：
輸入n個整數(shù)虫几，找出其中最小的K個數(shù)肺稀。例如輸入4,5,1,6,2,7,3,8這8個數(shù)字鳍侣，則最小的4個數(shù)字是1,2,3,4丁稀。

返回的也是一個數(shù)組，所以我們可以先全排列倚聚，然后返回前k個好了线衫。但是這樣的時間是O(nlgn)，有沒有比這更快的呢惑折。當(dāng)然有授账，下面介紹兩種方法。

1.利用快排中獲取分割點的方法惨驶。
如果輸入的數(shù)組可以修改白热，那么我們就可以使用這個方法。具體如下粗卜，我們使用快排的時候找根據(jù)priovt來把整個數(shù)組分成大于priovt的和小于priovt的兩部分屋确，然后遞歸調(diào)用快排這樣可以把數(shù)組排序。但是在這里续扔，我們不需要遞歸的調(diào)用快排攻臀，我們只需要找到那個priovt就可以了，所以我們需要的就是不斷的分割知道分割成k個前面的和size-k個后面的纱昧。k的前面都比num[k]小就可以了刨啸，不需要排序。

代碼如下：

class Solution
{
public:
 int partition(vector<int>& input, int start, int end)
 {
     if(input.empty() || start> end) 
         return -1;
     int temp = input[end];
     int j = start -1;
     for(int i=start;i<end,++i)
     {
         if(input[i]<=temp)
         {
             ++j;
             if(i!=j) swap(input[i],input[j]);
         }
     }
     swap(input[j+1],input[end]);
     return j+1;
 }

 vector<int> GetLeastNumbers_Solution(vector<int> input, int k)
 {
     vector<int> res;
     if(input.empty() || k>input.size() || k<=0) 
         return res;
     int start = 0;
     int end = input.size()-1;
     int index = partition(input,start,end);
     while(index != k-1)
     {
         if(index>k-1)
         {
             end = index-1;
             index = partition(input,start,end);
         }
         else
         {
             start = index+1;
             index = partition(input,start,end); 
         }
     }
     for(int i=0;i<k;++i)
         res.push_back(input[i]);
     return res;
 }
}

這個方法的復(fù)雜度是O(n),因為第一次是n识脆，第二次就是n/2设联，加匈。。仑荐。

2.堆排序 O(nlgk)。
上面的算法會修改原來的輸入數(shù)組纵东，如果不能修改的話粘招，我們可以使用堆排序來解決。
方法是：創(chuàng)建一個K個節(jié)點的堆偎球，每次讀的時候比較一下洒扎，如果堆還沒有滿，那么讀入的數(shù)字就插進去衰絮，如果已經(jīng)滿了就按照大小來替換袍冷。所以我們可以用一個最大堆來存放數(shù)字，那么在這里就直接使用multiset了猫牡，因為set內(nèi)部是紅黑樹實現(xiàn)的胡诗。另外就是我們的輸入很可能是重復(fù)的，所以實用multi-

class Solution
{
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> res;
        if(input.empty() || k>input.size() || k<=0) 
            return res;
        multiset<int, greater<int> > numbers;
        multiset<int, greater<int>>::iterator first;
        for(vector<int>::iterator it = input.begin();it!=input.end();++it)
        {
            if(numbers.size()<k)
                numbers.insert(*it);
            else
            {
                first = numbers.begin();
                if(*it < *(numbers.begin()))
                {
                    numbers.erase(first);
                    numbers.insert(*it);
                }
            }
        }
        for(first=numbers.begin();first!=numbers.end();++first)
            res.push_back(*first);
        return res;
    }
}