大家好我是苏麟 , 今天带来堆的一些经典问题 , 我们一起研究一下 .
大纲
- 数组中的第K个最大元素
- 合并 K 个升序链表
数组中的第K个最大元素
描述 :
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
题目 :
LeetCode 215. 数组中的第K个最大元素 :
数组中的第K个最大元素
分析 :
这个题是一道非常重要的题，主要解决方法有三个，选择法，堆查找法和快速排序法
选择法很简单，就是先遍历一遍找到最大的元素，然后再遍历一遍找第二大的，然后再遍历一遍找第三大的，直到第K次就找到了目标值了。但是这种方法只适合在面试的时候预热，面试官不会让你这么简单就开始写代码，因为该方法的时间复杂度为O(NK)。
比较好的方法是堆排序法和快速排序法。快速排序我们已经分析过，这里先看堆排序如何解决问题
这个题其实用大堆小堆都可以解决的，但是我们推荐“找最大用小堆，找最小用大堆，找中间用两个堆”，这样更容易理解，适用范围也更广。
我们可以使用idk的优先队列来解决，其思路是很简单的。由于找第K大元素，其实就是整个数组排序以后后半部分最小的那个元素。因此，我们可以维护一个有K 个元素的最小堆:
- 如果当前堆不满，直接添加;
- 堆满的时候，如果新读到的数小于等于堆顶，肯定不是我们要找的元素，只有新遍历到的数大于堆顶的时候，才将堆顶拿出，然后放入新读到的数，进而让堆自己去调整内部结构。
官方题解
解析 :
class Solution {
public int findKthLargest(int[] nums, int k) {
if(k > nums.length){
return -1;
}
PriorityQueue<Integer> pq = new PriorityQueue<>(k);
int length = nums.length;
for(int i = 0;i < k;i++){
pq.add(nums[i]);
}
for(int i =k;i < length;i++){
Integer temp = pq.peek();
if(temp < nums[i]){
pq.poll();
pq.add(nums[i]);
}
}
return pq.peek();
}
}
合并 K 个升序链表
描述 :
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
题目 :
LeetCode 23. 合并 K 个升序链表 :
合并 K 个升序链表
分析 :
我们看堆排序如何解决。因为每个队列都是从小到大排序的，我们每次都要找最小的元素，所以我们要用小根堆，构建方法和操作与大顶堆完全一样，不同的是每次比较谁更小。使用堆合并的策略是不管几个链表，最终都是按照顺序来的。每次都将剩余节点的最小值加到输出链表尾部，然后进行堆调整，最后堆空的时候，合并也就完成了还有一个问题，这个堆应该定义为多大呢? 给了几个链表，堆就定义多大。
解析 :
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists == null || lists.length == 0){
return null;
}
PriorityQueue<ListNode> pq = new PriorityQueue<>(Comparator.comparing(node -> node.val));
for(int i = 0;i< lists.length;i++){
if(lists[i] != null){
pq.add(lists[i]);
}
}
ListNode list = new ListNode(-1);
ListNode p = list;
while(!pq.isEmpty()){
ListNode temp = pq.poll();
p.next = temp;
p = p.next;
if(p.next != null){
pq.add(p.next);
}
}
return list.next;
}
}
这期就到这里 , 下期见!
