先把前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]);
}
|