AcWing 5960:输出前k大的数 ← 小根堆
【题目来源】
https://www.acwing.com/problem/content/5963/
【题目描述】
给定一个长度为 n 的数组 a1,a2,…,an,统计前 k 大的数并且把这 k 个数从大到小输出。
【输入格式】
第一行包含整数 n。
第二行包含 n 个整数 a1,a2,…,an。
第三行包含整数 k。
【输出格式】
从大到小输出前 k 大的数,每个数一行。
【数据范围】
1≤n≤10^5,
−10^9≤ai≤10^9,
1≤k≤n
【输入样例】
10
4 5 6 9 8 7 1 2 3 0
5
【输出样例】
9
8
7
6
5
【算法分析】
● vector<int> arr(n); 是创建了一个包含n个int元素的vector,每个元素会被默认初始化为0。
【算法代码】
#include <bits/stdc++.h>
using namespace std;
priority_queue<int, vector<int>, greater<int>> L; //小根堆
priority_queue<int> G; //大根堆
int main() {
int n,k;
cin>>n;
vector<int> arr(n);
for(int i=0; i<n; i++) {
cin>>arr[i];
}
cin>>k;
for(int x:arr) {
if(L.size()<k) L.push(x);
else if(x>L.top()) {
L.pop();
L.push(x);
}
}
while(!L.empty()) {
G.push(L.top());
L.pop();
}
while(!G.empty()) {
cout<<G.top()<<endl;
G.pop();
}
return 0;
}
/*
in:
10
4 5 6 9 8 7 1 2 3 0
5
out:
9
8
7
6
5
*/
【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/119813940
https://blog.csdn.net/hnjzsyjyj/article/details/146315528
https://www.acwing.com/solution/content/258025/