这题用最小堆来解过不了吗

P1923 【深基9.例4】求第 k 小的数

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 kn 同阶。


by 小小小朋友 @ 2023-03-28 20:35:30

@QGmzb 加上ios::sync_with_stdio(0)可过


|