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，如需转载请自行联系原作者