leetcode: the Kth largest element in the array

215. 数组中的第K个最大元素

难度中等1787

给定整数数组 nums 和整数 k,请返回数组中第 **k** 个最大的元素.

请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素.

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题.

示例 1:

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

示例 2:

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

提示：

• 1 <= k <= nums.length <= 105
• -104 <= nums[i] <= 104

这道题有多种解法

思路一：

Sort this array first,然后返回第kLarger elements can be subscripted.

//第一种写法
class Solution {
    
public:
    int findKthLargest(vector<int>& nums, int k) {
    
        sort(nums.begin(), nums.end());
        return nums[nums.size() - k];
    }
};

//第二种写法
class Solution {
    
public:
    int findKthLargest(vector<int>& nums, int k) {
    
        sort(nums.rbegin(), nums.rend());
        return nums[k - 1];
    }
};

//第三种写法
class Solution {
    
public:
    int findKthLargest(vector<int>& nums, int k) {
    
        sort(nums.begin(), nums.end(), greater<int>());
        return nums[k - 1];
    }
};

思路二：

Use priority queues,Sort the elements of the array into a priority queue,默认为大堆,然后进行 k - 1次的 pop Falling head position,最后第 k A big number is in the opposite position！

class Solution {
    
public:
    int findKthLargest(vector<int>& nums, int k) {
    
        //Put the data in the array into the priority queue first,默认为大堆
        priority_queue<int> p(nums.begin(), nums.end());

        //将队列中前k-1个最大的元素pop掉
        for(int i = 0; i < k - 1; ++i)
        {
    
            p.pop();
        }

        return p.top();
    }
};

时间复杂度：O(K + K*logN)

时间复杂度：O(N)

So when this array is big,May cause insufficient memory,So you can look at the optimal liberation below.

思路三（最优解法）：

Different from the second idea,This time we use priority queue storage k 个数,而且是按small heap storage！

Then let the remaining elements in the array be compared with the head in turn,If it is bigger than the opponent,则入堆,反之则跳过,依次循环,直到数组遍历完成.

class Solution {
    
public:
    int findKthLargest(vector<int>& nums, int k) {
    
        //创建kA small heap of space
        priority_queue<int, vector<int>, greater<int>> p(nums.begin(), nums.begin() + k);
        //Put the data larger than the top of the heap into the heap each time
        for(size_t i = k; i < nums.size(); ++i)
        {
    
            if(nums[i] > p.top())
            {
    
                p.pop();
                p.push(nums[i]);
            }
        }
        return p.top();
    }
};

This solution isKWhen it is very large, the time complexity is similar to that of the second idea：*O(K + (N - K)logK)

But the optimization of space complexity is very large：O(K)