题目：
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
思路：
1、排序
把输入的n个整数排序，然后取前k个数；
时间复杂度：O(nlogn)
2、Partition
通过partition找到第k大的数，它的左边就是前k小的数；
时间复杂度：O(n)
3、最大堆
构建k个整数的最大堆数据结构，然后将剩余n-k个整数依次与堆顶比较，大则抛弃，小则删除堆顶并插入，最后的最大堆就是最小的k个整数；
堆是基于二叉树来实现的，因此插入和删除操作都在O(logk)时间内完成。在代码中可以通过STL中的容器来实现，如set，multiset,priority_queue等，都是基于红黑树实现的，所以是排序的。
时间复杂度：O(nlogk)
代码：
1、Partition方法
#include <iostream>
using namespace std;
int Partition(int* numbers,int start,int end){
int key=numbers[start];
int i=start;
int j=end;
while(i<j){
while(i<j && numbers[j]>=key)
--j;
if(i<j) numbers[i++]=numbers[j];
while(i<j && numbers[i]<=key)
++i;
if(i<j) numbers[j--]=numbers[i];
}
numbers[i]=key;
return i;
}
void GetLeastNumbers(int* input,int n,int* output,int k){
if(input==NULL || output==NULL || k>n || n<=0 || k<=0)
return;
int start=0;
int end=n-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++)
output[i]=input[i];
}
int main()
{
int A[]={4,5,1,6,2,7,3,8};
int len=sizeof(A)/sizeof(A[0]);
int k=4;
GetLeastNumbers(A,len,A,k);
for(int i=0;i<k;i++)
cout<<A[i]<<" ";
cout<<endl;
return 0;
}
2、最大堆/大顶堆
#include <iostream>
#include <set>
#include <vector> using namespace std; typedef multiset<int,greater<int> > inSet;
typedef multiset<int,greater<int> >::iterator setIterator; void GetLeastNumbers_1(const vector<int> &data,inSet &leastNumbers,unsigned int k){
leastNumbers.clear(); if(k<1 || data.size()<k)
return; vector<int>::const_iterator it=data.begin();
for(;it!=data.end();it++){
if(leastNumbers.size()<k)
leastNumbers.insert(*it);
else{
setIterator iterGreatest=leastNumbers.begin();
if(*it<*iterGreatest){
leastNumbers.erase(iterGreatest);
leastNumbers.insert(*it);
}
}
}
} int main()
{
int A[]={4,5,1,6,2,7,3,8};
int len=sizeof(A)/sizeof(A[0]);
int k=4;
vector<int> data(A,A+len); inSet leastNumbers;
GetLeastNumbers_1(data,leastNumbers,k); for(setIterator it=leastNumbers.begin();it!=leastNumbers.end();it++)
cout<<*it<<" ";
cout<<endl; return 0;
}
在线测试OJ：
http://www.nowcoder.com/books/coding-interviews/6a296eb82cf844ca8539b57c23e6e9bf?rp=2
AC代码：
1、Partition方法：
class Solution {
public:
int Partition(vector<int> &data,int start,int end){
int key=data[start];
int i=start;
int j=end;
while(i<j){
while(i<j && data[j]>=key)
j--;
if(i<j)
data[i++]=data[j];
while(i<j && data[i]<=key)
i++;
if(i<j)
data[j--]=data[i];
}
data[i]=key;
return i;
}
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
vector<int> output;
if(k<1 || input.size()<k)
return output;
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++)
output.push_back(input[i]);
return output;
}
};
2、大顶堆:multiset
class Solution {
public:
typedef multiset<int,greater<int> > inSet;
typedef multiset<int,greater<int> >::iterator inSetIterator;
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
vector<int> output;
if(k<1 || input.size()<k)
return output;
inSet LeastNumbers;
for(vector<int>::iterator it=input.begin();it!=input.end();it++){
if(LeastNumbers.size()<k)
LeastNumbers.insert(*it);
else{
inSetIterator greatest=LeastNumbers.begin();
if(*it<*greatest){
LeastNumbers.erase(*greatest);
LeastNumbers.insert(*it);
}
}
}
for(inSetIterator it=LeastNumbers.begin();it!=LeastNumbers.end();it++)
output.push_back(*it);
return output;
}
};3、大顶堆：priority_queue
class Solution {
public:
typedef priority_queue<int,vector<int>,less<int> > PQ;
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
vector<int> output;
if(k<1 || input.size()<k)
return output;
PQ LeastNumbers;
for(vector<int>::iterator it=input.begin();it!=input.end();it++){
if(LeastNumbers.size()<k)
LeastNumbers.push(*it);
else{
int greatest=LeastNumbers.top();
if(*it<greatest){
LeastNumbers.pop();
LeastNumbers.push(*it);
}
}
}
while(!LeastNumbers.empty()){
output.push_back(LeastNumbers.top());
LeastNumbers.pop();
}
return output;
}
};