leetcode hot100【LeetCode 215.数组中的第K个最大元素】java实现
LeetCode 215.数组中的第K个最大元素标题形貌
给定一个整数数组 nums 和一个整数 k，请返回数组中第 k 个最大的元素。
请留意，要求排名是从大到小的，因此第 k 个最大元素是排序后的第 k 个元素。你需要计划一个高效的算法来办理这个问题。
示例 1：
输入：nums = , k = 2
输出：5
表明：数组中第二大的元素是 5。
示例 2：
输入：nums = , 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大的元素
}
}
解题思绪
[*] 最小堆方法： 我们可以利用最小堆（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 = ，我们要求第 2 大的元素。
[*]初始数组：，k = 2
[*]创建一个大小为 2 的最小堆：
[*]插入 3，堆为
[*]插入 2，堆为 （因为堆是最小堆，所以自动调整）
[*]插入 1，堆为 （删除最小元素 2）
[*]插入 5，堆为 （删除最小元素 1）
[*]插入 6，堆为 （删除最小元素 3）
[*]插入 4，堆为 （删除最小元素 4）
[*]终极堆中元素为 ，堆顶为 5，即第 2 大元素。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]