题目描述

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素。
示例：

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

解题思路

方法1：使用快排，每次返回当前正确归位元素的下标，直至下标与'k'一致。

    int partition(vector<int>& nums, int start, int end){
        int small = start - 1;
        for(int idx=start; idx<end; idx++){
            if(nums[idx]<nums[end]){
                small++;
                swap(nums[small], nums[idx]);
            }
        }
        small++;
        swap(nums[small], nums[end]);
        return small;
    }
    int findKthLargest(vector<int>& nums, int k) {
        k = nums.size() - k;
        int start = 0, end = nums.size() - 1;
        int index = partition(nums, start, end);
        
        while(index!=k){
            if(index>k)
                end = index - 1;
            else
                start = index + 1;
            index = partition(nums, start, end);
        }
        return nums[index];
    }

时间复杂度为O(n)，空间复杂度O(1)

同样，快排方法也可以用于无序数组查找最大、最小值，相比于遍历整个数组要稍微优化一些。

方法2：维护一个大小为k的小顶堆，不断将数组元素喂进去，直至结束。最后返回堆顶。

    int findKthLargest(vector<int>& nums, int k) {
        //升序的优先队列
        priority_queue <int,vector<int>,greater<int> > ascending;
        for (int &i:nums)
        {
            ascending.push(i);
            if (ascending.size()>k)
                ascending.pop();
        }
        return ascending.top();
    }

时间复杂度为O(nlog(k))，空间复杂度为O(k)。