题解 | #寻找第K大#

(1)没有满足题意，使用优先队列求解

class Solution {
public:
    int findKth(vector<int> a, int n, int K) {
        // write code here
        priority_queue<int, vector<int>, greater<int>> pq;
        
        for(int i=0; i<K; i++){
            pq.push(a[i]);
        }
        
        for(int i=K; i<n; i++){
            if(pq.top() < a[i]){
                pq.pop();
                pq.push(a[i]);
            }
        }
        
        int res = pq.top();
        return res;
    }
};

（2）满足题意，采用类似快速排序思路

class Solution {
public:
    int findKth(vector<int> a, int n, int K) {
        // write code here
        cal(a, 0, n-1, K);
        return a[K-1];
    }
    
    void cal(vector<int>& a, int left, int right, int k){
        if(left > right){
            return;
        }
        
        int temp = a[left];
        int i = left, j = right;
        
        while(i != j){
            while(a[j] <= temp && i<j) j--;
            while(a[i] >= temp && i<j) i++;
            if(i < j){
                int t = a[i];
                a[i] = a[j];
                a[j] = t;
            }
        }
        
        a[left] = a[i];
        a[i] = temp;
       
        if(i >= k){
            cal(a, left, i-1, k);
        }
        else{
            cal(a, i+1, right, k);
        }
        
    }
    
    
};