【数据结构与算法 | 堆篇】力扣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 <= 104
• 0 <= 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();}
}