堆
搞一个小根堆,把所有元素都放到堆中,每次弹出堆顶元素,第k个堆顶元素就是答案。
复杂度$O(nlogn)$
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
priority_queue<int, vector<int>, greater<int> > q;
int n, k;
int a[100010];
int main() {
cin >> n >> k;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
q.push(x);
}
int cnt = 0;
while (!q.empty()) {
int x = q.top();
q.pop();
cnt++;
if (cnt == k) {
printf("%d\n", x);
break;
}
}
return 0;
}
还是堆
维护一个大小为K的大根堆,当堆大小小于K时元素直接入堆。
堆大小为K时,堆顶元素大于当前元素时,弹出堆顶,并放入当前元素。
因为是大根堆,堆顶元素是堆中的最大值,新元素比堆顶小。
此时堆中的K个数和新来的数这K+1个数中,堆顶最大,是第K+1个数,一定不会是答案,所以弹出去。
这样就保证了堆中的元素一定是最小的K个,那么最后堆顶元素就是第K小数。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
priority_queue<int> q;
int n, k;
int main() {
cin >> n >> k;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
if (q.size() < k) {
q.push(x);
}
else if (q.top() > x) {
q.pop();
q.push(x);
}
// printf("x=%d, q.top()=%d\n", x, q.top());
}
cout << q.top() << endl;
return 0;
}