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

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

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

• 提示：

1 <= k <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4

思路

使用堆排序来解决寻找数组中第 k 个最大的元素问题是一种常见的方式，特别是最小堆或最大堆数据结构可以高效地找到第 k 大的元素。这里我们使用最小堆来解题，因为我们只需要维护一个大小为 k 的堆，这样堆顶元素就是当前第 k 大的元素。

1. 先创建一个最小堆，将前 k 个元素加入堆中。最小堆的堆顶始终是当前堆中的最小元素。
2. 对于数组中剩下的元素（从第 k+1 个元素开始），如果元素比堆顶元素大，替换堆顶元素并重新调整堆。
3. 最终堆顶的元素就是第 k 大的元素。

• 时间复杂度:O(log₂k)
• 空间复杂度:O(k)

代码

public int findKthLargest(int[] nums, int k) {
    // 创建一个最小堆
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    // 将前 k 个元素加入最小堆
    for (int i = 0; i < k; i++) {
        minHeap.offer(nums[i]);
    }
    // 对于第 k+1 个元素开始，如果当前元素比堆顶元素大，替换堆顶并重新调整
    for (int i = k; i < nums.length; i++) {
        if (nums[i] > minHeap.peek()) {
            minHeap.poll();
            minHeap.offer(nums[i]);
        }
    }
    // 最终堆顶的元素就是第 k 大的元素
    return minHeap.peek();
}