网站验证码系统,龙岗网站建设设计服务,计算机专业里面哪个专业最好,手机怎么做程序LeetCode 215.数组中的第K个最大元素
题目描述
给定一个整数数组 nums 和一个整数 k#xff0c;请返回数组中第 k 个最大的元素。
请注意#xff0c;要求排名是从大到小的#xff0c;因此第 k 个最大元素是排序后的第 k 个元素。你需要设计一个高效的算法来解决这个问题。…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大的元素PriorityQueueInteger 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 大元素。
