题意概括

给定一个长度为 $N$ 的整数数组和一个整数 $K$，要求找出数组中第 $K$ 个最大的元素。

数据范围:

• $1 \le K \le N \le 10^5$
• 数组中的元素为整数。

基础知识

解决这个问题最经典的方法有以下几种：

1. 排序法: 这是最直观的思路。将整个数组从大到小排序，然后直接取出索引为 $K-1$ 的元素即可。这种方法的时间复杂度主要由排序算法决定，通常为 $O(N \log N)$。

2. 优先队列 (堆): 维护一个大小为 $K$ 的数据容器。我们可以使用最小堆（Min-Heap）。遍历数组中的每个元素，将其插入堆中。如果堆的大小超过了 $K$，就将堆顶（也就是堆中最小的元素）弹出。当整个数组遍历完毕后，堆顶的元素就是我们要求的第 $K$ 大的元素。时间复杂度为 $O(N \log K)$。

3. 快速选择算法: 这是快速排序算法的一个变种。它的核心思想是，每次选择一个基准元素 (pivot)，将数组分区为两部分：小于等于基准的元素和大于基准的元素。然后根据基准元素在分区后的位置，判断第 $K$ 大的元素位于哪个子数组中，并递归地只对那个子数组进行处理。该算法的平均时间复杂度为 $O(N)$，但最坏情况下的时间复杂度为 $O(N^2)$。C++ STL 中的 std::nth_element 函数提供了该算法的高效实现。

对于本题的数据规模，$O(N \log K)$ 和 $O(N)$ 的解法都是非常理想的。下面将采用优先队列的方式来实现。

C++ 解决方案

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void slv() {
    int n, k;
    cin >> n >> k;

    // 最小堆，用于维护当前看到的K个最大元素
    priority_queue<int, vector<int>, greater<int>> pq;

    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        pq.push(x);

        // 如果堆的大小超过K，就弹出堆顶的最小元素
        if (pq.size() > k) {
            pq.pop();
        }
    }

    // 遍历结束后，堆顶就是第K大的元素
    cout << pq.top() << endl;
}

int main() {
    // 关闭同步流，加速IO
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    slv();

    return 0;
}

/*
样例输入 1:
6 2
3 2 1 5 6 4

样例输出 1:
5

样例输入 2:
9 4
3 2 3 1 2 4 5 5 6

样例输出 2:
4
*/