临沂消防建设局官方网站,seo排名优化怎么样,四川建设网和四川省公共资源交易信息网,网站全站模板1. 力扣215 : 数组中的第k个最大元素
(1). 题
给定整数数组 nums 和整数 k#xff0c;请返回数组中第 k 个最大的元素。
请注意#xff0c;你需要找的是数组排序后的第 k 个最大的元素#xff0c;而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解…1. 力扣215 : 数组中的第k个最大元素
(1). 题
给定整数数组 nums 和整数 k请返回数组中第 k 个最大的元素。
请注意你需要找的是数组排序后的第 k 个最大的元素而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1:
输入: [3,2,1,5,6,4], k 2
输出: 5示例 2:
输入: [3,2,3,1,2,4,5,5,6], k 4
输出: 4提示
1 k nums.length 105-104 nums[i] 104
(2). 思路1
工具类直接无脑秒了.
(3). 解1
class Solution {public int findKthLargest(int[] nums, int k) {Arrays.sort(nums);return nums[nums.length - k];}
}
(4). 思路2
利用优先队列再秒. 使用了比较器每次poll出的是数值最大的元素.
(5). 解2
class Solution {public int findKthLargest(int[] nums, int k) {PriorityQueueInteger pq new PriorityQueue((o1, o2) - {return o2 - o1;});for (int i 0; i nums.length; i) {pq.offer(nums[i]);}for (int i 0; i k - 1; i) {pq.poll();}return pq.peek();}
}
(6). 思路3
构造大顶堆思路如上. 不加比较器的优先级队列底层就是用小顶堆实现的.
(7). 解3
class Solution {public int findKthLargest(int[] nums, int k) {Heap heap new Heap(nums.length);heap.heapify(nums);return heap.sort(k);}
}
//大顶堆
class Heap{//堆的大小private int size;int[] heap;public Heap(int capacity) {heap new int[capacity];}//堆化public void heapify(int[] nums) {for (int i 0; i nums.length; i) {heap[i] nums[i];}size nums.length;//从最后一个非叶子节点开始, 下沉for (int parent (size - 1) / 2; parent 0; parent--) {int leftChild parent*21;int rightChild parent*22;int max parent;//如果左孩子存在, 而且左孩子比父亲还要大if (leftChild size heap[leftChild] heap[max]) {max leftChild;}//如果右孩子存在, 而且左孩子比父亲和左孩子还要大if (rightChild size heap[rightChild] heap[max]){max rightChild;}if (max ! parent) {down(parent);}}}public void down(int parent) {int leftChild parent*21;int rightChild parent*22;int max parent;if (leftChild size heap[leftChild] heap[max]) {max leftChild;}if (rightChild size heap[rightChild] heap[max]){max rightChild;}if (max ! parent) {swap(max, parent);down(max);}}private void swap(int max, int parent) {int temp;temp heap[max];heap[max] heap[parent];heap[parent] temp;}public int sort(int k) {int n size;while (size 1){swap(0, size-1);size--;down(0);}size n;return heap[size - k];}
}
