最小的k个数

问题：
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。

返回的也是一个数组，所以我们可以先全排列，然后返回前k个好了。但是这样的时间是O(nlgn)，有没有比这更快的呢。当然有，下面介绍两种方法。

1.利用快排中获取分割点的方法。
如果输入的数组可以修改，那么我们就可以使用这个方法。具体如下，我们使用快排的时候找根据priovt来把整个数组分成大于priovt的和小于priovt的两部分，然后递归调用快排这样可以把数组排序。但是在这里，我们不需要递归的调用快排，我们只需要找到那个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;
 }
}

这个方法的复杂度是O(n),因为第一次是n，第二次就是n/2，。。。

2.堆排序 O(nlgk)。
上面的算法会修改原来的输入数组，如果不能修改的话，我们可以使用堆排序来解决。
方法是：创建一个K个节点的堆，每次读的时候比较一下，如果堆还没有满，那么读入的数字就插进去，如果已经满了就按照大小来替换。所以我们可以用一个最大堆来存放数字，那么在这里就直接使用multiset了，因为set内部是红黑树实现的。另外就是我们的输入很可能是重复的，所以实用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;
    }
}