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

一、题目

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

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

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

二、题解

思路：维护一个大小为 $K$ 的最小堆 (Min-Heap)

我们要找的是“第 K 大”的元素。很多人的直觉是使用最大堆，但其实找第 K 大，应该用最小堆。

逻辑如下：

1. 我们创建一个最小堆，并限制它最多只能装 $k$ 个元素。
2. 遍历数组，把元素依次扔进堆里。
3. 一旦堆里的元素数量超过了 $k$，我们就把堆顶元素（也就是当前堆里最小的那个元素）踢出去。
4. 这样一套流程走完，那些较小的元素全被踢出去了，堆里留下的正是整个数组中最大的 $k$ 个元素。
5. 既然堆里装的是最大的 $k$ 个元素，而这是一个最小堆，那么堆顶（这 $k$ 个数里面最小的一个）不正好就是第 K 大的元素吗？

import java.util.PriorityQueue;

class Solution {
    public int findKthLargest(int[] nums, int k) {
        // 创建一个最小堆
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        for (int num : nums) {
            minHeap.offer(num); // 将当前元素加入堆中

            // 如果堆的大小超过了 k，就弹出堆顶元素（也就是踢掉最小的）
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }

        // 遍历结束后，堆里剩下的是最大的 k 个元素
        // 堆顶就是这 k 个元素中最小的，也就是全局第 k 大的元素
        return minHeap.peek();
    }
}

时间复杂度：$O(n \log k)$

空间复杂度：$O(k)$