题解 | #寻找第K大#

最开始的想法很简单，直接食用sort()将数组排序，然后直接通过序号取第K大的元素即可。sort()使用的是优化后的快速排序，所以时间复杂度平均为O(nlogn)，空间复杂度为O(logn)。
不满足题目要求，此时注意到题目中还特意给出了数组大小n，可能需要用到别的解法才能达到题目要求。

class Solution {
public:
    int findKth(vector<int> a, int n, int K) {
        // write code here
        sort(a.begin(),a.end());
        return a.at(a.size()-K);
    }
};

在查阅相关资料后并未找到空间复杂度为O(1)的解法，如果说不借助辅助变量，则快速排序可满足，但快速排序的递归深度较大，虽不借助辅助变量，但递归的栈深度使其空间复杂度为O(logn)。当然，上面给出的简短的两行代码当然并非最优解，还有较大优化空间。
一种优化方法是在快排基础之上优化，每趟快排都查看分界元素的位置，若大于K，则只对左侧元素排序，若小于K则只对右侧元素排序，这样每趟递归都可以减少一定的时空复杂度。代码如下。从最终运行结果来看，运行时间上是有明显提升的，而运行空间上的提升则较小。这种优化方法要求必须熟练手搓快排，对基础有一定要求。像我老是偷个懒用库函数的，写起来就坑比较多。还是那句话，基础不牢，地动山摇。
另一种优化方法是使用堆排序，这种方法仅在数据量足够大时才可被称为优化。

class Solution {
public:
    int qs(vector<int>& a,int low, int high,int k){
        if(high <= low){
            return a.at(k-1);
        }
        int i = low;
        int j = high+1;
        while(1){
            while(a.at(++i) > a.at(low)){
                if(i == high){
                    break;
                }
            }
            while(a.at(--j) < a.at(low)){
                if(j == low){
                    break;
                }
            }
            if(i>=j){
                break;
            }
            int temp = a.at(i);
            a.at(i) = a.at(j);
            a.at(j) = temp;
        }
        int tmp = a.at(low);
        a.at(low) = a.at(j);
        a.at(j) = tmp;
        if(j == k-1){
            return a.at(j);
        }
        if(j > k-1){
            return qs(a,low,j-1,k);
        }
        if(j < k-1){
            return qs(a,j+1,high,k);
        }
        return 0;

    }
    int findKth(vector<int> a, int n, int K) {
        // write code here
        return qs(a, 0, n-1, K);
    }
};