题解 | #寻找第K大#

快速选择(Quickselect)算法，快速排序的近亲。C++ STL的nth_element正是这个功能。

时间复杂度O(N)，空间复杂度O(1)，题目的O(NlogN)有问题。

public:
    int findKth(vector<int> a, int n, int K) {
        vector<int>::iterator target_pos = a.begin() + K - 1;
        nth_element(a.begin(), target_pos, a.end(), greater<int>());
        return a[K - 1];
    }
};