社区讨论

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

P1923【深基9.例4】求第 k 小的数参与者 3已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@lo2uyaak
此快照首次捕获于
2023/10/23 20:12
2 年前
此快照最后确认于
2023/10/23 20:12
2 年前
查看原帖
今天刚学完最小堆,我的思路是建立一个最小堆,删除堆顶元素k次,最后取出堆顶元素即可得到第k小的数,时间复杂度为O(n+klogn),若k远小于n则时间复杂度趋近于O(n)。结果最后两个测试点超时了,是测试数据的k给的太大了吗? 附代码:
CPP
#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];
}

回复

2 条回复,欢迎继续交流。

正在加载回复...