先把前K个数建成一个最小堆heap，然后依次考虑第K+1,K+2...个数，如果第K+i个数小于heap[0],就把heap[0]从堆中删除，同时把地k+i个数加入堆中。这样，每次插入堆的时间复杂度为O(lgk)，总的时间复杂度为O(n*lgK)
 #include<iostream>
#include<algorithm>
using namespace std;
#define maxn 100
  int a[]= {3,5,1,56,2,5,2,561,56,154,1,56,1,5,15,2,52,62523,56,126,1,52,6}; //23 62523 561 154 126 56
int heap[100];
bool cmp(const int & a,const int & b)
{
 return a>b;
 }
int main()
{
int len,i;
for(i=len=0;i<5;i++)
  {
heap[len++]=a[i];
push_heap(heap,heap+len,cmp);
 }
for(;i<23;i++)
{
if(heap[0]<a[i])
{
pop_heap(heap,heap+len,cmp);
heap[len-1]=a[i];
push_heap(heap,heap+len,cmp);
}
}
for(i=0;i<5;i++)
printf("%d\n",heap[i]);
}
|