题解 | #寻找第K大#

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 * };
 * [1,3,5,2,2],5,3
 */
//#维护一个长度为k的数组，升序有序
class Solution {
private:
    vector<int> k_array;
    void updateArray(int val, int K){
        if(k_array.size()<K){
            k_array.push_back(val);
            for(int i=k_array.size()-1; i>0; i--){
                if(k_array[i]<k_array[i-1]){
                    int tmp = k_array[i];
                    k_array[i] = k_array[i-1];
                    k_array[i-1] = tmp;
                }
            }
        }else{
            bool changed = false;
            for(int i = 1; i <k_array.size(); i++) {
                if(val<=k_array[i]){
                    k_array[i-1] = val;
                    changed = true;
                    break;
                }else{
                    k_array[i-1] = k_array[i];
                }
            }
            if(!changed){
                k_array[k_array.size()-1] = val;
            }
        }
    }

public:
    int findKth(vector<int> a, int n, int K) {
        // write code here


        for(int i = 0; i <n; i++) {
            if(k_array.size()<K || a[i]>k_array[0]){
                updateArray(a[i], K);
            }
        }

        return k_array[0];

    }
};