leetcode215. 数组中的第K个最大元素（C++|优先队列|堆）

链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array/

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

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

示例 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 <= 104
-104 <= nums[i] <= 104

手确实生疏了，这道题目想着排序肯定是可以做的，但是堆也行，只是自己不会实现。看了一下题解，提到优先队列，可以，用小顶堆很巧妙，当容量大于K时，我们只需要pop出队头元素，那肯定是比第k大小的，我们不需要考虑它。堆可以用优先队列来实现，不需要自己写，但是也要有能力写对哦。默认的是大顶堆，即less，优先级越高越出队，从大到小进行排序；小顶堆用greater，优先级越高越出队，因此最小的元素在队头，他是优先级最高的。

priority_queue, less> q1;//大顶堆，队头元素最大，从大到小进行排序
priority_queue, greater> q2; //小顶堆，队头元素最小，从小到大进行排序

空间复杂度O(1)时间复杂度O(nlogN) :遍历元素，乘上堆出入队的时间 代码

class Solution {
public:

    int findKthLargest(vector& nums, int k) {
        // 利用优先队列来做
        priority_queue,greater> pq;//小顶堆，从小到大进行排序
        for(int i=0;ik){
                pq.pop();
            }
        }
        //cout< 
参考链接：【STL】c++优先队列(priority_queue)用法详解_bandaoyu的note-CSDN博客
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5714641.html