网站建设作业过程,葫芦岛做网站,企业网站 phpcms,做网站的软件 简单易学题目#xff1a;
给定整数数组 nums 和整数 k#xff0c;请返回数组中第 k 个最大的元素。
请注意#xff0c;你需要找的是数组排序后的第 k 个最大的元素#xff0c;而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
方法一#xff…题目
给定整数数组 nums 和整数 k请返回数组中第 k 个最大的元素。
请注意你需要找的是数组排序后的第 k 个最大的元素而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
方法一内部 api 排序
class Solution {public int findKthLargest(int[] nums, int k) {Arrays.sort(nums);int n nums.length;return nums[n - k];}
} 方法二堆排序
class Solution {public int findKthLargest(int[] nums, int k) {PriorityQueueInteger heap new PriorityQueue(); // 小顶堆for (int num : nums) {heap.offer(num);if (heap.size() k) // 让堆始终保持k个元素,多于k时让堆顶即最小的出heap.poll(); // 出堆顶,即最小的元素}return heap.peek(); // 返回堆顶元素}
}
小顶堆每个节点的值都小于或等于其左右孩子的值
大顶堆每个节点的值都大于或等于其左右孩子的值
