215. 数组中的第K个最大元素
快速排序
class Solution {
public:int findKthLargest(vector<int>& a, int k) {auto qsort = [&](this auto&& qsort, int l, int r) -> void {if (l == r) return;int i = l - 1, j = r + 1;int x = a[(l + r) / 2];/*如果把>改成>=，<改成<=，相同的数不就不交换，不就变成稳定的排序了？实际上坚决不可以这样做，因为一旦x是整个数列里最大的数，i向右移动，是找不到大于x的数的，就会越界，除非增加很多判断语句，要么限制x的越界，要么特判相等时不交换*/while (i < j) {do {i++;} while (a[i] < x);do {j--;} while (a[j] > x);if (i < j) swap(a[i], a[j]);}/*注意这里边界是j，和二分法一样记住就行了，特别的细节*/qsort(l, j);qsort(j + 1, r);};qsort(0, (int)a.size() - 1);return a[a.size() - k];}
};
线性时间选择
class Solution {
public:int findKthLargest(vector<int>& a, int k) {auto qsort = [&](this auto&& qsort, int l, int r, int k) -> int {if (l == r) return a[k];int i = l - 1, j = r + 1;int x = a[(l + r) / 2];while (i < j) {do {i++;} while (a[i] < x);do {j--;} while (a[j] > x);if (i < j) swap(a[i], a[j]);}if (k <= j) return qsort(l, j, k);else return qsort(j + 1, r, k);};return qsort(0, (int)a.size() - 1, (int)a.size() - k);}
};平均复杂度O（n）：
在分解的过程当中，我们会对子数组进行划分，如果划分得到的 q 正好就是我们需要的下标，就直接返回 a[q]；否则，如果 q 比目标下标小，就递归右子区间，否则递归左子区间。这样就可以把原来递归两个区间变成只递归一个区间，提高了时间效率。这就是「快速选择」算法。
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。需要注意的是，这个时间复杂度只有在 随机数据 下才成立，而对于精心构造的数据则可能表现不佳。因此我们这里并没有真正地使用随机数，而是使用双指针的方法，这种方法能够较好地应对各种数据。
347. 前 K 个高频元素
class Solution {
public:vector<int> topKFrequent(vector<int>& a, int k) {map<int, int> mp;for (auto x : a) mp[x]++;vector<pair<int, int>> v;vector<int> ans;for (auto [x, y] : mp) {v.push_back({ y, x });}sort(v.begin(), v.end(), greater<>());for (int i = 0; i < k; i++) {ans.push_back(v[i].second);}return ans;}
};
295. 数据流的中位数
class MedianFinder {
public:priority_queue<int, vector<int>, less<int>> q1; //大根堆priority_queue<int, vector<int>, greater<int>> q2;int sz;MedianFinder() {sz = 0;}void addNum(int x) {if (q2.empty() || x >= q2.top()) q2.push(x);else q1.push(x);sz++;while (q2.size() > (sz + 1) / 2) q1.push(q2.top()), q2.pop();while (q2.size() < (sz + 1) / 2) q2.push(q1.top()), q1.pop();}double findMedian() {if (sz & 1) return q2.top();else return (q1.top() + q2.top() + 0.0) / 2;}
};对顶堆板子题，这是动态求第k大的模板（k可变化）