【数据结构与算法 | 堆篇】力扣215, 703
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) {PriorityQueue<Integer> 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*2+1;int rightChild = parent*2+2;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*2+1;int rightChild = parent*2+2;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大的元素, 因为堆下面的元素都大于堆首PriorityQueue<Integer> 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();}
}