当前位置：首页 > article >正文

算法通关村第十四关-白银挑战堆的经典问题

article 2024/11/16 22:26:00

大家好我是苏麟 , 今天带来堆的一些经典问题 , 我们一起研究一下 .

大纲

- 数组中的第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;
    }
}