LeetCode215 数组中的第K个最大的数

梦里梦外; 2023-10-04 21:24 20阅读 0赞

#### 目录 ####

*  题目描述
 *  思路
 *   *  堆
 *  代码

## 题目描述 ##

给定整数数组 `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

## 思路 ##

大多数排序算法的时间复杂度都是O(nlogn)或者O(n^2)，所以排序后再输出`k`下标的方法不可行。  
那么这题我们可以通过维护一个堆来解决。

### 堆 ###

堆是什么？  
1.首先堆可以视为一颗完全二叉树。  
2.其次堆中某个节点的值总是不大于（或不小于）其父节点的值。  
所以堆的根节点(顶端)是该堆中最大或者最小的节点。根节点最大的堆被称为大顶堆，根节点最小的堆则是小顶堆。

借助这样的性质，我们维护一个大小为`k`的小顶堆，依次将数组中的元素入堆，如果超过堆初始大小`k`了，就将堆顶的元素移出。因为每次移出的都是当前堆中的最小元素，也就是说在`n-k`次移出堆顶后，此时的堆顶就是第`n-k`小的数，也就是我们要的第`k`个最大的数。

## 代码 ##

class Solution {
        
        public int findKthLargest(int[] nums, int k) {
        
            int n = nums.length;
            PriorityQueue<Integer> heap = new PriorityQueue<>();// 默认小顶堆
            for (int i = 0; i < n; i++) {
        
                heap.offer(nums[i]);
                if (heap.size()>k){
        
                    heap.poll();
                }
            }
            return heap.peek(); // 返回堆顶
        }
    }