#include<iostream>
#include<cstdlib>
using namespace std;
void SwAp(int &a,int &b){
int tmp=a;
a=b;
b=tmp;
}
int FindKthLargest(int *num,int k,int left,int right){
int base=num[left];//基准数
int L=left,R=right;
while(1){
while((left<=right)&&(base<=num[left])) left++;
while((left<right)&&base>num[right]) right--;
if(left<right){
SwAp(num[left],num[right]);
}else break;
}
SwAp(num[left-1],num[L]);
if((left-L-1)>=k) return FindKthLargest(num,k,L,left-2);
else if((left-L-1)<k-1) return FindKthLargest(num,k-(left-L-1)-1,left,R);
else return base;
}
int main(){
int N,k;
while(cin>>N>>k){
int *num=(int *)malloc(N*sizeof(int));
for(int i=0;i<N;i++){
cin>>num[i];
if(i+1>=k){
int result=FindKthLargest(num,k,0,i);
cout<<result<<endl;
}
}
free(num);
}
return 0;
}
优化递归算法在该题的时间损耗
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
- 邀请回答
-
2条回答 默认 最新
- _GX_ 2022-02-18 23:56关注
这题用优先队列做更简单
#include <iostream> #include <queue> #include <vector> using namespace std; int main() { int n, k; while (cin >> n >> k) { vector<int> a(n); for (int i = 0; i < n; i++) cin >> a[i]; priority_queue<int, vector<int>, std::greater<int>> queue; for (int i = 0; i < k; i++) queue.push(a[i]); cout << queue.top() << '\n'; for (int i = k; i < n; i++) { queue.push(a[i]); queue.pop(); cout << queue.top() << '\n'; } } return 0; }
本回答被题主选为最佳回答 , 对您是否有帮助呢?解决 无用评论 打赏 举报
悬赏问题
- ¥15 linux驱动,linux应用,多线程
- ¥20 我要一个分身加定位两个功能的安卓app
- ¥15 基于FOC驱动器,如何实现卡丁车下坡无阻力的遛坡的效果
- ¥15 IAR程序莫名变量多重定义
- ¥15 (标签-UDP|关键词-client)
- ¥15 关于库卡officelite无法与虚拟机通讯的问题
- ¥15 目标检测项目无法读取视频
- ¥15 GEO datasets中基因芯片数据仅仅提供了normalized signal如何进行差异分析
- ¥100 求采集电商背景音乐的方法
- ¥15 数学建模竞赛求指导帮助