问题：
输入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;
}
}
