/*
This is a free Program, You can modify or redistribute it under the terms of GNU
*Description:一种查找k个最小元素的方法
*Language: C++
*Development Environment: VC6.0
*Author: Wangzhicheng
*E-mail: 2363702560@qq.com
*Date: 2012/11/25
*/
#include <iostream>
#include <vector>
#include <set>
#include <ctime>
#include <algorithm>
using namespace std;
/*
*此种方法原理比较简单,即利用一个空间大小是k的multiset
*将原始数据的前k个依次插入multiset,然后从元素数据的第k+1个元素开始
*逐渐与multiset的第一个元素比较,(注意,multiset是用红黑树实现的,可以容纳
*多个相同的元素,当比较器是greater时,multiset第一个元素是最大的元素),如果比
*第一元素小,则删除mutiset第一个元素,将此元素插入
*/
template<class Type>
class FindKMinElemFromVector {
public:
void Method_Of_SortedK(vector<Type>&v,int k) {
multiset<Type,greater<Type> >assistant;
vector<Type>::iterator it;
for(it=v.begin();it!=v.begin()+k;it++) {
assistant.insert(*it);
}
for(;it!=v.end();it++) {
multiset<Type,greater<Type> >::iterator Max_it=assistant.begin();
if(*it<*Max_it) {
assistant.erase(Max_it); //此时不能写成*Max_it,这样会删除多个相同的元素
assistant.insert(*it);
}
}
multiset<Type,greater<Type> >::iterator it1;
cout<<k<<"个最小数据是:"<<endl;
for(it1=assistant.begin();it1!=assistant.end();it1++) {
cout<<*it1<<" ";
}
cout<<endl;
}
};
void main() {
FindKMinElemFromVector<int>ff;
srand(unsigned(time(0)));
int N=20;
int i=0;
vector<int>v;
int x;
for(i=0;i<N;i++) {
v.push_back(rand()%N);
}
cout<<"原始数据是:"<<endl;
copy(v.begin(),v.end(),ostream_iterator<int>(cout," "));
cout<<endl;
ff.Method_Of_SortedK(v,3);
}
测试：
