优先队列

这题也可以用优先队列写， 建立一个最大堆，先输入m个值，此时最大堆的堆顶就是第m大的值，然后对之后n - m的数进行操作，如果n - m的某一值x小于堆顶，将堆顶元素抛出， x进队, 如此反复，最后堆顶的答案就是第k个小数。

C++ 代码

#include<iostream>
#include<queue>
using namespace std;
priority_queue<int, vector<int>, less<int> > q;
int main(){
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int x;
        cin >> x;
        q.push(x);
    }
    for(int i = m; i < n; i++){
        int x;
        cin >> x;
        if(x < q.top()){
            q.push(x);
            q.pop();
        }
    }
    cout << q.top() << endl;
    return 0;
}