基于链表结构的 求第 k大的数，时间效率O(n) （广陵，我把代码贴了）
之前出的题目，基于链表结构，在O(n)的时间里面求第k大的数。到现在为止都没看到让我满意的代码。
现在应广陵之前之邀把代码贴出来。
不足的地方，请指正。
程序代码：
#include<iostream>
#include<cstdlib>
#include<utility>
#include<cassert>
using std::pair;
template<class Type>
class List
{
public:
struct Node{
Type val;
Node():pre(this),next(this){}
Node(Type key):pre(this),next(this)
{
val=key;
}
Node(Node &node)
{
this->val=node.val;
}
Node &operator=(Node & node)
{
this->val=node.val;
}
~Node()
{
}
friend std::ostream & operator<<(std::ostream &os,Node &node)
{
os<<node.val<<" ";
return os;
}
Node* pre;
Node* next;
};
typedef Node* iter;
List()
{
tail=new Node();
}
virtual ~List(){
destroy();
assert( tail->next==tail);
delete tail;
}
std::size_t size();
virtual void insert(Type key);
virtual void erase(iter it);
iter begin(){ return tail->next;}
iter end(){ return tail;}
void walk();
protected:
void swap(Node &n1,Node &n2)
{
Node tmp=n1;
n1=n2;
n2=tmp;
}
void destroy();
private:
iter tail;
};
template<class Type>
void List<Type>::insert(Type key)
{
if( NULL==tail )
{
tail=new Node(key);
tail->pre=tail;
tail->next=tail;
}
else
{
iter it=new Node(key);
it->pre=tail->pre;
it->pre->next=it;
it->next=tail;
it->next->pre=it;
}
}
template<class Type>
void List<Type>::erase(iter it)
{
it->pre->next=it->next;
it->next->pre=it->pre;
delete it;
}
template<class Type>
std::size_t List<Type>::size()
{
if( tail==tail->next)
return 0;
else
{
std::size_t sz=0;
for(iter it=begin();it!=end();it=it->next)
{
sz++;
}
return sz;
}
}
template<class Type>
void List<Type>::walk()
{
iter it=tail;
if( NULL != tail)
{
for(it=tail->next;it!=tail;it=it->next)
{
std::cout<<*it<<" ";
}
std::cout<<std::endl;
}
}
template<class Type>
void List<Type>::destroy()
{
for(List<Type>::iter it=begin();it !=end();it=it->next)
{
erase(it);
}
}
template<class Type>
class Rank:public List<Type>{
public:
Rank():List<Type>(){}
void qsort()
{
sort(1,List<Type>::size(),List<Type>::begin(),(List<Type>::end())->pre);
}
typename List<Type>::Node * _rank_k(int k);
~Rank(){}
protected:
pair<typename List<Type>::Node*,int>
partition(int p,int r,typename List<Type>::Node * pt,typename List<Type>::Node* rt)
{
Type x=rt->val;
int i=p-1,j;
typename List<Type>::Node* it;
typename List<Type>::Node* jt;
it=pt->pre;
jt=pt;
for(j=p;j<r;j++)
{
if(jt->val<=x)
{
i=i+1;
it=it->next;
swap(*it,*jt);
}
jt=jt->next;
}
swap(*(it->next),*rt);
return std::make_pair(it->next,i+1);
}
void sort(int p,int r,typename List<Type>::Node* pt,typename List<Type>::Node* rt)
{
if( p< r )
{
pair<typename List<Type>::Node*,int> qt;
qt=partition(p,r,pt,rt);
sort(p,qt.second-1,pt,qt.first->pre);
sort(qt.second+1,r,qt.first->next,rt);
}
}
typename List<Type>::Node* select(int p,int r,int i,typename List<Type>::Node* pt,typename List<Type>::Node* rt);
};
template<class Type>
typename List<Type>::Node * Rank<Type>::_rank_k(int k)
{
assert(k+1<=List<Type>::size() &&k+1>0);
return select(1,List<Type>::size(),k+1,List<Type>::begin(),List<Type>::end());
}
template<class Type>
typename List<Type>::Node*
Rank<Type>::select(int p,int r,int i,typename List<Type>::Node*pt,typename List<Type>::Node * rt)
{
if( p == r )
{
return pt;
}
pair<typename List<Type>::Node *,int>qt;
qt=partition(p,r,pt,rt);
int k=(qt.second)-p+1;
if( i == k )
return qt.first;
else if( i< k)
return select(p,qt.second-1,i,pt,qt.first->pre);
else
return select(qt.second+1,r,i-k,qt.first->next,rt);
}
int main()
{
srand(time(NULL));
Rank<int> rank;
for(int i=0;i<10;i++)
{
int key=rand()%50;
rank.insert(key);
}
rank.walk();
//std::cout<<rank.size()<<std::endl;
std::cout<<*(rank._rank_k(5))<<std::endl;
//rank.qsort();
//rank.walk();
return 0;
}编译器g++ 4.0以上。
