C++ Exercises（十）
1.1 找出第K大的数
方法1：
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;
int main()
{
int data[] = {3,54,254,52,13,667,234,67,256,78,467,32,65,324,889,34,5};
int len = sizeof(data)/sizeof(int);
vector<int> v1(data,data+len);
ostream_iterator<int> out(cout," ");
copy(v1.begin(),v1.end(),out);
cout<<endl;
sort(v1.begin(),v1.end(),greater<int>());
copy(v1.begin(),v1.end(),out);
cout<<endl;
int k;
cin>>k;
cout<<v1[k-1]<<endl;
system("pause");
return 0;
}
方法2：
#include <iostream>
#include <list>
#include <algorithm>
#include <iterator>
using namespace std;
class LessThan
{
public:
LessThan(int val):value(val){}
~LessThan(){}
bool operator()(int rhs)
{
return rhs<=value;
}
private:
int value;
};
int main()
{
int data[] = {3,54,254,52,475,667,234,67,256,78,467,32,65,324,889,34,5};
int len = sizeof(data)/sizeof(int);
int k;
cin>>k;
list<int> list1(data,data+k);
ostream_iterator<int> out(cout," ");
list1.sort(greater<int>());//对前K个数进行排序
list<int>::iterator pos;
for(int i=k;i<len;++i)
{
if(data[i]>list1.back())
{//比最后一个元素大
pos = find_if(list1.begin(),list1.end(),LessThan(data[i]));//找到第一个比要插入值小的元素位置
list1.insert(pos,data[i]);//插入新值
list1.pop_back();//删除最后一个多余的元素
}
}
copy(list1.begin(),list1.end(),out);
cout<<endl;
cout<<"第"<<k<<"大的数是: "<<endl;
int count = 1;
for(pos = list1.begin();pos!=list1.end();++pos,++count)
{
if(count==k)
cout<<(*pos)<<endl;
}
system("pause");
return 0;
}
方法3：用最大堆排序
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;
template<typename T>
void HeapAdjust(vector<T> &v,size_t start,size_t end)
{
T tmp = v[start];
size_t s = start;
for(size_t j=(2*s+1);j<=end;j=(2*j+1))
{
if(j<end&&v[j+1]>v[j])
j++;
if(tmp<v[j])
{
v[s] = v[j];
s = j;
}
}
v[s] = tmp;
}
template<typename T>
void Swap(T &a,T &b)
{
T tmp = a;
a = b;
b = tmp;
}
template<typename T>
void HeapSort(vector<T> &v)
{
int i = 0,j=0;
//建最大堆
for(i=(v.size()-1)/2;i>=0;--i)
{
HeapAdjust(v,i,v.size()-1);
}
cout<<"输入K:"<<endl;
int k;
cin>>k;
for(i=v.size(),j=k;i>1&&j>0;--i,--j)
{
Swap(v[0],v[i-1]);
if(j==1)
{
cout<<v[i-1];
}
else
{
HeapAdjust(v,0,i-2);
}
}
}
int main()
{
int data[]={93,5,233,55,3,67,2,67,32,6,89,355};
int len = sizeof(data)/sizeof(int);
vector<int> v1(data,data+len);
HeapSort(v1);
return 0;
}
本文转自Phinecos(洞庭散人)博客园博客，原文链接：http://www.cnblogs.com/phinecos/archive/2008/03/31/1131862.html，如需转载请自行联系原作者
