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 实现代码
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大的元素}
}
解题思路
最小堆方法: 我们可以利用最小堆(
PriorityQueue
)来实现。堆是一个完全二叉树,可以在O(logn)
时间内进行插入和删除操作。
- 将数组中的前
k
个元素插入到最小堆中。- 如果当前堆中元素个数大于k,则吐出。
- 最后,堆顶的元素就是第
k
大的元素。这种方法的时间复杂度是
O(n log k)
,其中n
是数组的大小,k
是需要找到的第k
大元素。快速选择法: 另一种方法是使用快速排序的思想,即快速选择(Quickselect)。通过对数组进行划分,选择性地进入有可能包含第
k
大元素的子数组。这个方法的平均时间复杂度是O(n)
。
复杂度分析
- 时间复杂度: 使用最小堆方法时,插入一个元素的时间复杂度是
O(log k)
,所以对于数组中n
个元素,总的时间复杂度是O(n log k)
。- 空间复杂度:
O(k)
,因为堆中最多存储k
个元素。
举例说明执行过程
假设有数组
nums = [3,2,1,5,6,4]
,我们要求第2
大的元素。
- 初始数组:
[3,2,1,5,6,4]
,k = 2
- 创建一个大小为
2
的最小堆:
- 插入
3
,堆为[3]
- 插入
2
,堆为[2, 3]
(因为堆是最小堆,所以自动调整)- 插入
1
,堆为[1, 3]
(删除最小元素2
)- 插入
5
,堆为[3, 5]
(删除最小元素1
)- 插入
6
,堆为[5, 6]
(删除最小元素3
)- 插入
4
,堆为[5, 6]
(删除最小元素4
)- 最终堆中元素为
[5, 6]
,堆顶为5
,即第2
大元素。