题目描述
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。
#include <iostream>
#include <vector>
#include <set>;
using namespace std;
void findKMaxnum(vector<int> vec,int k){
set<int> s;
for(int i=0;i<k;i++)
s.insert(vec[i]);
int len=vec.size();
set<int>::iterator it;
for(int i=k;i<len;i++){
it=s.end();
it--;
if(*it>vec[i]){
s.erase(it);
s.insert(vec[i]);
}
}
}
int main(){
int a[10]={5,7,4,8,1,2,9,3,6,0};
vector<int> vec(a,a+10);
findKMaxnum(vec,4);
system("pause");
}
思路：
基于堆排序算法，构建最大堆。时间复杂度为O(nlogk)
如果用快速排序，时间复杂度为O(nlogn)
如果用冒泡排序，时间复杂度为O(n*k)