社区讨论
这题用最小堆来解过不了吗
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 条回复,欢迎继续交流。
正在加载回复...