Leetcode215 数组中的第K个最大元素

小咪咪 2022-10-16 14:21 148阅读 0赞

#### 题目描述 ####

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

#### 思路解析 ####

1.  如果直接排序，输出第K个最大元素的话，会超时
2.  利用小顶堆实现，堆的时间复杂度低，而自己实现一个堆比较麻烦，可以通过现成的基于堆实现的有序队列`priority_queue`来实现
3.  对于2，思想在于利用堆的特性：保持小顶堆有K个元素，最小的在堆顶，依次遍历数组，如果元素比堆顶还小，就不可能是第K大。

#### Java实现 ####

class Solution {
        
        public int findKthLargest(int[] nums, int k) {
        
            // 优先队列默认是小顶堆
            Queue<Integer> queue = new PriorityQueue<>();
            for (int i = 0; i < nums.length; i++) {
        
                // 维持堆中有固定k个最大的数
                if(queue.size()<k){
        
                    queue.add(nums[i]);
                }else{
        
                    if(queue.peek()<nums[i]){
        
                        // 替换
                        queue.remove();
                        queue.add(nums[i]);
                    }
                }
            }
            return queue.remove();

#### C++ 实现 ####

class Solution {
        
    public:
        int findKthLargest(vector<int>& nums, int k) {
        
            // 升序队列，从而内部实现是一个小顶堆。
            priority_queue<int,vector<int>,greater<int>> q;
            for(int i=0;i<nums.size();i++)
            {
        
                // 放元素，会自动堆排序
                q.push(nums[i]);
                // 如果超过K个数，
                if(q.size()>k)
                {
        
                    q.pop();
                }
            }
           return q.top();
        }
    };