做网站推广有前景吗,网站开发一年多少钱,做外贸必备网站,一个人注册公司需要什么条件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];}
}
2. 力扣703 : 数据流中的第k大元素
(1). 题
设计一个找到数据流中第 k 大元素的类class。注意是排序后的第 k 大元素不是第 k 个不同的元素。
请实现 KthLargest 类
KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。int add(int val) 将 val 插入数据流 nums 后返回当前数据流中第 k 大的元素。
示例
输入
[KthLargest, add, add, add, add, add]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
输出
[null, 4, 5, 5, 8, 8]解释
KthLargest kthLargest new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3); // return 4
kthLargest.add(5); // return 5
kthLargest.add(10); // return 5
kthLargest.add(9); // return 8
kthLargest.add(4); // return 8提示
1 k 1040 nums.length 104-104 nums[i] 104-104 val 104最多调用 add 方法 104 次题目数据保证在查找第 k 大元素时数组中至少有 k 个元素
(2). 思路
思路都在题解上.
(3). 解
public class KthLargest {//优先队列的底层实现是小顶堆, 所以将该堆的大小维持在k个长度时, //取堆首元素, 就是堆第k大的元素, 因为堆下面的元素都大于堆首PriorityQueueInteger pq new PriorityQueue();int k1;public KthLargest(int k, int[] nums) {//add方法中需要使用k, 所以用k1记录k的值k1 k;int i;//如果k nums.length, 分成两个部分判断//如果k nums.length, 力扣该题9个案例似乎都是这种情况//只有一种情况, 即k比nums数组的长度大一个长度, 所以add以后k就可以取到第k大的元素if (k nums.length) {for (i 0; i k; i) {pq.offer(nums[i]);}for (i k ; i nums.length; i) {//如果该数组的元素要比堆首元素要大, //将堆首元素移除, 加入该数组元素.//堆首元素就是新的第k大的元素if (nums[i] pq.peek()) {pq.poll();pq.offer(nums[i]);}}} else {for (i 0; i nums.length; i) {pq.offer(nums[i]);}}}public int add(int val) {//此时k比堆的大小要大一个, 直接将该元素入堆即可if (k1 pq.size()) {pq.offer(val);} else {if (val pq.peek()) {pq.poll();pq.offer(val);}}return pq.peek();}
}
