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

题目描述

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

请注意，要求排名是从大到小的，因此第 k 个最大元素是排序后的第 k 个元素。你需要设计一个高效的算法来解决这个问题。

示例 1：

输入：nums = [3,2,1,5,6,4], k = 2
输出：5
解释：数组中第二大的元素是 5。

示例 2：

输入：nums = [3,2,3,1,2,4,5,5,6], k = 4
输出：4
解释：数组中第四大的元素是 4。

Java 实现代码

class Solution {public int findKthLargest(int[] nums, int k) {// 使用最小堆来找第k大的元素PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);for (int num : nums) {minHeap.offer(num);if (minHeap.size() > k) {minHeap.poll(); // 维护堆的大小为k，去除堆中最小的元素}}return minHeap.peek(); // 最小堆的根就是第k大的元素}
}

解题思路

1. 最小堆方法： 我们可以利用最小堆（PriorityQueue）来实现。堆是一个完全二叉树，可以在 O(logn) 时间内进行插入和删除操作。

   • 将数组中的前 k 个元素插入到最小堆中。
   • 如果当前堆中元素个数大于k，则吐出。
   • 最后，堆顶的元素就是第 k 大的元素。

   这种方法的时间复杂度是 O(n log k)，其中 n 是数组的大小，k 是需要找到的第 k 大元素。

2. 快速选择法： 另一种方法是使用快速排序的思想，即快速选择（Quickselect）。通过对数组进行划分，选择性地进入有可能包含第 k
   大元素的子数组。这个方法的平均时间复杂度是 O(n)。

复杂度分析

• 时间复杂度: 使用最小堆方法时，插入一个元素的时间复杂度是 O(log k)，所以对于数组中 n 个元素，总的时间复杂度是 O(n log k)。
• 空间复杂度: O(k)，因为堆中最多存储 k 个元素。

举例说明执行过程

假设有数组 nums = [3,2,1,5,6,4]，我们要求第 2 大的元素。

1. 初始数组：[3,2,1,5,6,4]，k = 2
2. 创建一个大小为 2 的最小堆：
   • 插入 3，堆为 [3]
   • 插入 2，堆为 [2, 3]（因为堆是最小堆，所以自动调整）
   • 插入 1，堆为 [1, 3]（删除最小元素 2）
   • 插入 5，堆为 [3, 5]（删除最小元素 1）
   • 插入 6，堆为 [5, 6]（删除最小元素 3）
   • 插入 4，堆为 [5, 6]（删除最小元素 4）
3. 最终堆中元素为 [5, 6]，堆顶为 5，即第 2 大元素。