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

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

解题思路

使用一个最小堆来维护当前最大的K个元素。遍历数组中的每个元素，将其加入堆中，如果堆的大小超过K，则移除堆顶元素（即当前最小的元素）。最终，堆顶元素就是第K个最大的元素。

当前时间复杂度为: $O(n \log k)$，其中n是数组的长度，k是需要找到的第K个最大元素的数量。空间复杂度为: $O(k)$，因为堆中最多存储K个元素。

题解。如果需要优化时间复杂度，可以使用快速选择算法（Quickselect），平均时间复杂度为$O(n)$，但最坏情况下可能退化到$O(n^2)$。

参考代码

class Solution {
    public int findKthLargest(int[] nums, int k) {
        Queue<Integer> queue = new PriorityQueue<>();

        for(int num : nums) {
            queue.offer(num);
            if(queue.size() > k) {
                queue.poll();
            }
        }

        return queue.poll();
    }
}