215. 数组中的第K个最大元素（数组与哈希）

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

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

//第一种写法
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];
    }
};

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        //将数组里面的数据先放到优先级队列中，默认为大堆
        priority_queue<int> p(nums.begin(), nums.end());
 
        //将队列中前k-1个最大的元素pop掉
        for(int i = 0; i < k - 1; ++i)
        {
            p.pop();
        }
 
        return p.top();
    }
};

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        //创建k个空间的小堆
        priority_queue<int, vector<int>, greater<int>> p(nums.begin(), nums.begin() + k);
        //将每次大于堆顶的数据入堆
        for(size_t i = k; i < nums.size(); ++i)
        {
            if(nums[i] > p.top())
            {
                p.pop();
                p.push(nums[i]);
            }
        }
        return p.top();
    }
};