// 最小的k个数.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include <iostream>
#include <set>
#include <vector>
#include <queue>
using namespace std;
// set中默认是从大到小的顺序,即最先取出的是最小值
// 此处为从小到大,最先取出的是最大值
typedef multiset<int,greater<int>> inSet;
typedef multiset<int,greater<int>>::iterator setIterator;
// 基于红黑树
void GetNumber(vector<int> &data,inSet &leastNumber,int k)
{
if(k<= || data.size()==)
return ;
leastNumber.clear();
vector<int>::iterator it = data.begin();
for(;it!=data.end();++it)
{
if(leastNumber.size()<k)
leastNumber.insert(*it);
else{
setIterator s = leastNumber.begin();
if(*it < *s)
{
leastNumber.erase(s);
leastNumber.insert(*it);
}
}
}
setIterator s = least.begin();
for(;s!=least.end();++s)
cout<<*s<<" ";
cout<<endl;
}
// 基于优先队列
void GetNumber2(vector<int> &data,int k)
{
if(data.size()== || k<)
return ;
// top取出的是最小值,即是按从大到小排列的
//priority_queue<int,vector<int>,greater<int>> q;
// 默认是从小到大排列,即最先取出的是最大值
priority_queue<int> q;
vector<int>::iterator it = data.begin();
for(;it!=data.end();++it)
{
if(q.size()<k)
q.push(*it);
else{
if(*it < q.top())
{
q.pop();
q.push((*it));
}
}
}
while(q.size()>)
{
cout<<q.top()<<" ";
q.pop();
}
cout<<endl;
}
int Partition(int *a,int start,int end)
{
if(start < end)
{
int i=start,j=end;
int x = a[start];
while(i<j)
{
while(i<j && a[j]>x)
j--;
if(i<j)
a[i++] = a[j];
while(i<j && a[i]<x)
i++;
if(i<j)
a[j--] = a[i];
}
a[i] = x;
return i;
}
}
// 基于分治思想,但会修改数组,时间复杂度为O(N)
void GetNumber2(int *a,int len,int k)
{
if(a==NULL || len<= || k<=)
return ;
int start = ,end = len-;
int index = Partition(a,start,end);
//取出最小的K个数
while(index != k-)
{
if(index < k-)
{
start = index +;
index = Partition(a,start,end);
}else{
end = index -;
index = Partition(a,start,end);
}
}
for(int i=;i<k;++i)
cout<<a[i]<<" ";
cout<<endl;
}
int _tmain(int argc, _TCHAR* argv[])
{
vector<int> v;
v.push_back();
v.push_back();
v.push_back();
v.push_back();
v.push_back();
v.push_back();
v.push_back();
inSet least;
GetNumber1(v,least,);
GetNumber2(v,);
int a[]={,,,,,,,};
GetNumber2(a,,);
system("pause");
return ;
}