堆能高效解决的经典问题(算法村第十四关白银挑战)

发布时间:2024年01月24日

数组中的第K个最大元素

215. 数组中的第K个最大元素 - 力扣(LeetCode)

给定整数数组 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

小根堆

第 K 个最大元素,就是在数组排序以后,后 K 个元素中最小的元素。因此,我们可以维护一个有 K 个元素的小根堆:

  1. 堆不满时,直接往堆中添加元素;
  2. 堆满时,如果新读到的数小于或等于堆顶,那肯定不是我们要找的元素,只有新遍历到的数大于堆顶的时候,才将堆顶拿出,然后放入新读到的数,进而让堆自己去调整内部结构。
public int findKthLargest(int[] nums, int k)
{
    //创建一个容量为 k 的小根堆
    PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);
    //将前k个元素(含)加入小根堆
    for (int i = 0; i < k; i++)
        minHeap.add(nums[i]);

    //遍历剩余的元素,进行替换操作
    for (int i = k; i < nums.length; i++)
    {
        //如果当前元素大于堆顶元素,则替换堆顶元素
        if (nums[i] > minHeap.peek())
        {
            minHeap.poll();
            minHeap.offer(nums[i]);
        }
    }

    //返回堆顶元素,即第k大元素
    return minHeap.peek();
}

注:PriorityQueue中元素的默认排序是升序排序。这意味着队列头部的元素(堆顶元素)将是最小的元素。如果需要改变排序顺序,例如创建大根堆,可以通过传递一个比较器Comparator.reverseOrder()来实现降序排列。

重要结论

找第K大用小根堆,找第K小用大根堆。

就本题来说:

  1. K多大就建立多大的堆
  2. 建立小跟堆小根堆
  3. 只有比堆顶大元素的才让进入堆

合并 K 个升序链表

23. 合并 K 个升序链表 - 力扣(LeetCode)

给你一个链表数组,每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中,返回合并后的链表。

示例 1:

输入:lists = [[1,4,5],[1,3,4],[2,6]]
输出:[1,1,2,3,4,4,5,6]
解释:链表数组如下:
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

题解

23. 合并 K 个升序链表 - 力扣(LeetCode)

堆排序

将所有节点放入小根堆

public static ListNode mergeKLists(ListNode[] lists)
{
    //创建一个小根堆,并设置比较器(这是必须的,不能采用默认的升序)
    PriorityQueue<ListNode> minHeap = new PriorityQueue<>((ListNode a,ListNode b)->(a.val - b.val));
    //将所有节点放入小根堆
    for(ListNode list : lists)
    {
        while(list != null)
        {
            minHeap.offer(list);
            list = list.next;
        }
    }

    //答案链表的虚拟头结点
    ListNode dummy = new ListNode(-1);
    //尾插法,保证升序
    ListNode tail = dummy;

    while (!minHeap.isEmpty())
    {
        tail.next = minHeap.poll();
        tail = tail.next;
    }

    tail.next = null;   //手动截断,否则会在输出方法中陷入死循环
    return dummy.next;
}

堆排序优化

先将每个链表的头节点放入小根堆,出来一个再放入下一个,这样可以维持一个小堆,减少堆的自我排序时间,也将原先的空间复杂度O(N)优化到O(k)

public static ListNode mergeKLists_2(ListNode[] lists)
{
    //创建一个小根堆,并设置比较器(这是必须的,不能采用默认的升序)
    PriorityQueue<ListNode> minHeap = new PriorityQueue<>((ListNode a,ListNode b)->(a.val - b.val));
    //先将每个链表的头节点放入小根堆
    for(ListNode list : lists)
        if (list != null)
            minHeap.offer(list);

    //答案链表的虚拟头结点
    ListNode dummy = new ListNode(-1);
    //尾插法,保证升序
    ListNode tail = dummy;

    while (!minHeap.isEmpty())
    {
        ListNode node = minHeap.poll();
        tail.next = node;
        tail = tail.next;

        //把剩下的结点放入小根堆
        if(node.next != null)
            minHeap.offer(node.next);
    }

    tail.next = null;   //手动截断,否则会在输出方法中陷入死循环
    return dummy.next;
}
文章来源:https://blog.csdn.net/cjj2543107638/article/details/135832197
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。