QGmzb @ 2023-03-28 20:04:04
今天刚学完最小堆,我的思路是建立一个最小堆,删除堆顶元素k次,最后取出堆顶元素即可得到第k小的数,时间复杂度为O(n+klogn),若k远小于n则时间复杂度趋近于O(n)。结果最后两个测试点超时了,是测试数据的k给的太大了吗? 附代码:
#include<iostream>
#include<algorithm>
using namespace std;
struct Heap{
int* heap;
int n;
};
int leftchild(int pos)
{return 2*pos+1;}
int rightchild(int pos)
{return 2*pos+2;}
void siftdown(Heap *h,int pos){
while(!((pos>=(h->n)/2)&&(pos<h->n))){
int j=leftchild(pos);
int rc=rightchild(pos);
if(rc<h->n && h->heap[rc]<h->heap[j]) j=rc;
if(h->heap[pos]<h->heap[j]) return;
swap(h->heap[pos],h->heap[j]);
pos=j;
}
}
void remove(Heap* h){
swap(h->heap[0],h->heap[--h->n]);
if(h->n!=0) siftdown(h,0);
}
void buildheap(Heap* h){
for(int i=(h->n)/2-1;i>=0;i--) siftdown(h,i);
}
int main(){
int n;
int k;
cin>>n;
cin>>k;
int *arr=new int[n];
for(int i=0;i<n;++i) cin>>arr[i];
Heap h;
h.heap=arr;
h.n=n;
buildheap(&h);
for(int i=0;i<k;++i) remove(&h);
cout<<h.heap[0];
}
by Imiya @ 2023-03-28 20:24:22
@QGmzb
by 小小小朋友 @ 2023-03-28 20:35:30
@QGmzb 加上ios::sync_with_stdio(0)可过