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

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

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

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

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

示例 2:

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

提示：

• $ 1 \leq k \leq nums.length \leq 10^5 $
• $-10^4 \leq nums[i] \leq 10^4 $

解法一(优先队列)

思路分析

1. 利用优先队列自动排序的特性, 创建由小到大排序的优先队列;
2. 题目要求取第 k 个最大的元素, 即保证队列中的元素个数为 k, 此时队列的第一个元素满足题目要求, 返回即可
3. 在遍历的过程中, 将每个元素入队, 当队列元素超过 k 个, 则将不符合的元素(位置在队头)出队;
4. 在不考虑优先队列本身的时间复杂度情况下, 遍历数组时间复杂度为 O(n);

实现代码

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int len = nums.length;
        PriorityQueue<Integer> deque = new PriorityQueue<>((o1, o2) -> o1 - o2);
        for (int i = 0; i < nums.length; ++ i) {
            deque.add(nums[i]);
            if (deque.size() > k) {
                deque.poll();
            }
        }
        return deque.poll();
    }
}

运行结果:

2025/04/11 10:34:39

解答成功:

执行耗时:90 ms,击败了14.27% 的Java用户

内存消耗:60.5 MB,击败了5.02% 的Java用户

复杂度分析

• 时间复杂度: $O(n)$
• 空间复杂度: $O(n)$