题解 | #寻找第K大#

思路

本题是一个排序问题，可选的排序方案很多，其中冒泡、选择等O(n^2)时间的排序方案代价较高，选用快排、堆排、分治算法是比较省时的方案。直接调用c++内置sort函数是最好的办法。

###方法一：调用sort函数排序

class Solution {
public:
    static bool cmp(const int& a, const int& b) {    // 设定比较规则，大数靠前
        return a > b;
    }
    
    int findKth(vector<int> a, int n, int K) {       
        // write code here
        sort(a.begin(), a.end(), cmp);                // 将原数组重新排序
        return a[K-1];                                // 返回第k大的数字
    }
};

####复杂度分析

• 时间复杂度：O(NlogN)，排序时间
• 空间复杂度：O(logN)，sort函数内部机制包含快速排序算法的思想，因此空间复杂度和快排的空间代价相关。

###方法二：堆排序 使用最大堆的方案来进行排序也是很好的方案，这是求k大或k小的数字常用方法

class Solution {
public:
    int findKth(vector<int> a, int n, int K) {
        // write code here
        vector<int>::iterator iter;
        int i = 0;
        for(iter = a.begin(); K > 1; K--){
            make_heap(iter, a.end(), less<int>());    // 构建最大堆
            iter++;                                   // 每构建一次调整一次起始构建位置
        }
        make_heap(iter, a.end(), less<int>());        // 由于最后执行了一次iter++，还需要再构建一次最大堆
        return *iter;
    }
};

####复杂度分析

• 时间复杂度：O(KlogN)，构建一次最大堆O(logN)，访问K次，比整体排序时间更短
• 空间复杂度：O(1)，没有额外空间申请