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

r囧r小猫 2022-11-04 11:13 192阅读 0赞

## 出处 ##

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

## 题目 ##

在未排序的数组中找到第 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

说明:

你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

## 思路 ##

这里我用到了小顶堆来解决。  
维护一个优先队列（小顶堆），遍历数组加入到这个优先队列，当优先队列中的元素大于k时，就从堆顶弹出一个元素。也就是保持堆中最多只有k个元素，堆顶的元素刚好就是数组中第k大的元素（因为比这个元素小的都已经被弹出去了）。

## 代码 ##

class Solution {
        
    public:
        int findKthLargest(vector<int>& nums, int k) {
        
            priority_queue <int,vector<int>,greater<int> > q;
            for(vector<int>::iterator it=nums.begin();it!=nums.end();it++) 
            {
        
                q.push(*it);
                if(q.size()>k){
        
                    q.pop();
                }
            }
            return q.top();
        }
    };

## 运行结果 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70]

## 总结 ##

通过这道题学到了C++ STL中优先队列的用法

要注意c++ 中优先队列默认是大顶堆序，如果我们想将优先队列变成小顶堆序，需要在定义优先队列是作出相应的调整：

priority_queue<int> q_default;//默认是大顶堆序
    priority_queue<int,vector<int>,less<int> >q;//大顶堆
    priority_queue<int,vector<int>,greater<int> > q2;//小顶堆

最大堆得到的是升序，要用less  
最小堆得到的是降序，要用greater

### 参考文章： ###

1.  [优先队列 结构体使用详解 ][Link 1]
2.  [堆排序(排升序为啥建大堆，排降序为啥建小堆)][Link 2]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70]: /images/20221023/8f5f3dc9a3f547439092875aaf68f5b0.png
[Link 1]: https://www.acwing.com/blog/content/394/
[Link 2]: https://blog.csdn.net/Code_beeps/article/details/91488526