题解 | #寻找第K大#

优先队列（小顶堆）方法：

class Solution {
public:
    int findKth(vector<int> a, int n, int K) {
        // write code here
        priority_queue<int, vector<int>, greater<int> > que;
        for (int i = 0; i < K; ++i) {
            que.push(a[i]);  //创建大小为K的优先队列
        }
        for (int i = K; i < n; ++i) {
            if (que.top() < a[i]) {
                que.pop();
                que.push(a[i]);  // 更新优先队列
            }
        }
        return que.top();  // 返回堆顶，即第K大的数
    }
};

快速排序算法变形

class Solution {
public:
    int findKth(vector<int> a, int n, int K) {
        return K_quickSelect(a, K);
    }

    int K_quickSelect(vector<int>& input, int k) {
        int l = 0, r = input.size();
        while (l < r) {
            int p = partition(input, l, r);  // 分段
            if (p+1 == k) { // 找到第 k 大的数据
                return input[p]; // 返回 k 个最小值
            }
            if (p+1 < k) { // 右半部分
                l = p + 1;
            } 
            else {         // 左半部分
                r = p;
            }
        }
        return input[0];
    }
    int partition(vector<int>& input, int l, int r) {  // 分段实现
        int pivot = input[r-1];
        int i = l;
        for (int j = l; j < r-1; ++j) {
            if (input[j] > pivot) {
                swap(input[i++], input[j]);
            }
        }
        swap(input[i], input[r-1]);
        return i;
    }
};