我们先假设元素的数量不大，例如在几千个左右，在这种情况下，那我们就排序一下吧。在这里，快速排序或堆排序都是不错的选择，他们的平均时间复杂度都是 O（N * log2N）。然后取出前 K 个，O（K）。
总时间复杂度 O（N * log2N）+ O（K） = O（N * log2N）。
你一定注意到了，当 K=1 时，上面的算法也是 O（N * log2N）的复杂度，
而显然我们可以通过 N-1 次的比较和交换得到结果。上面的算法把整个数组都
进行了排序，而原题目只要求最大的 K 个数，并不需要前 K 个数有序，也不需
要后 N-K 个数有序。
怎么能够避免做后 N-K 个数的排序呢？我们需要部分排序的算法，选择排
序和交换排序都是不错的选择。把 N 个数中的前 K 大个数排序出来，复杂度是O（N * K）。
那一个更好呢？O（N * log2N）还是 O（N * K）？
这取决于 K 的大小，这是你需要在面试者那里弄清楚的问题。在 K（K < = log2N）较小的情况下，可以选择部分排序。
在下一个解法中，会通过避免对前 K 个数排序来得到更好的性能。
解法二：
回忆一下快速排序，快排中的每一步，都是将待排数据分做两组，其中一组
的数据的任何一个数都比另一组中的任何一个大，然后再对两组分别做类似的操
作，然后继续下去……
在本问题中，假设 N 个数存储在数组 S 中，我们从数组 S 中随机找出一个
元素 X，把数组分为两部分 Sa 和 Sb。Sa 中的元素大于等于 X，Sb 中元素小于 X。
这时，有两种可能性：
1. Sa中元素的个数小于K，Sa中所有的数和Sb中最大的K-|Sa|个元素（|Sa|指Sa
中元素的个数）就是数组S中最大的K个数。
2. Sa中元素的个数大于或等于K，则需要返回Sa中最大的K个元素。
这样递归下去，不断把问题分解成更小的问题，平均时间复杂度 O（N *
log2K）。
测试代码如下：
using namespace std;
const int N=8;
const int K=4;
swap(int &a,int &b)
{
int temp;
temp=a;
a=b;
b=temp;
}
int partition(int data[],int start,int end)
{
int index=start;
swap(data[index],data[end]);
int small=start-1;
for(index=start;index<end;++index)
{
if(data[index]>data[end])
{
++small;
if(small!=index)
swap(data[index],data[small]);
}
}
++small;
swap(data[small],data[end]);
return small;
}
int findk(int a[],int low,int high,int k)
{
if(low<high)
{
int q=partition(a,low,high);
int len=q-low+1;
if(len==k)
{
return q;
}
else if(len<k)
return findk(a,low,q-1,k);
else
return findk(a,q+1,high,k-len);
}
}
int main()
{
int data[N]={5,2,66,23,11,1,4,55};
findk(data,0,N-1,K);
for(int i=0;i<K;i++)
cout<<data[i]<<endl;
system("pause");
return 0;
}
using namespace std;
const int N=8;
const int K=4;
int find(int *a,int x)
{
int sum=0;
for(int i=0;i<N;i++)
{
if(a[i]>=x)
sum++;
}
return sum;
}
int getK(int *a,int max,int min)
{
while(max-min>1)
{
int mid=(max+min)/2;
int num=find(a,mid);
if(num>=K)
min=mid;
else
max=mid;
}
cout<<"end"<<endl;
return min;
}
int main()
{
int a[N]={54,2,5,11,554,65,33,2};
int x=getK(a,554,2);
for(int i=0;i<N;i++)
{
if(a[i]>=x)
cout<<a[i]<<" ";
}
getchar();
return 0;
}
using namespace std;
const int N=8;
const int K=4;
class CTopK
{
public:
CTopK();
~CTopK();
int* m_Data;
int GetTopK(int Data[],int nTop);
private:
void Clear();
void HeapAdjust(int nStart,int nLen);
void BuildHeap(int nLen);
};
CTopK::CTopK()
{
m_Data=NULL;
}
CTopK::~CTopK()
{
Clear();
}
void CTopK::Clear()
{
if(NULL!=m_Data)
{
delete[] m_Data;
m_Data=NULL;
}
}
int CTopK::GetTopK(int Data[],int nTop)
{
int fData;
int i=0;
Clear();
cout<<"please wait..."<<endl;
for(i=0;i<nTop;i++)
{
m_Data[i]=Data[i];
}
if(i<nTop)
{
nTop=i;
}
else
{
BuildHeap(nTop);
for(;i<N;i++)
{
if(fData>m_Data[0])
{
m_Data[0]=fData;
HeapAdjust(0,nTop);
}
}
}
for(i=0;i<nTop;i++)
{
cout<<m_Data[i]<<" ";
}
return 0;
}
void CTopK::HeapAdjust(int nStart,int nLen)
{
int nMinChild=0;
int fTemp;
while((2*nStart+1)<nLen)
{
nMinChild=2*nStart+1;
if((2*nStart+2)<nLen)
{
if(m_Data[2*nStart+2]<m_Data[2*nStart+1])
{
nMinChild=2*nStart+2;
}
}
if(m_Data[nStart]>m_Data[nMinChild])
{
fTemp=m_Data[nStart];
m_Data[nStart]=m_Data[nMinChild];
m_Data[nMinChild]=fTemp;
nStart=nMinChild;
}
else
{
break;
}
}
}
void CTopK::BuildHeap(int nLen)
{
int i=0;
for(i=nLen/2-1;i>=0;i--)
{
HeapAdjust(i,nLen);
}
}
int main(int argc,char *argv[])
{
int Data[N]={54,2,5,11,554,65,33,2};
CTopK topk;
topk.GetTopK(Data,K);
return 0;
}
{
sumCount += count[v];
if(sumCount >= k)
break;
}
return v;