算法通关村第十四关|白银|堆的高效

本文介绍: 原题：力扣215.之间用快速排序做过这道题，这次使用堆查找。找最大用小堆，找最小用大堆，找中间用两个堆。这道题用小堆，新元素插入的时候就替换根元素，然后重新构造小堆，构造完成后的根元素就是第 K 大的元素，不论要处理的元素有多少以及是否固定，小堆的长度都固定为 K ，且根元素就是第 K 大的元素。只有比根元素大的才让进入堆。这里使用 PriorityQueue 优先队列。

1.在数组中找第 K 大的元素

原题：力扣215.

之间用快速排序做过这道题，这次使用堆查找。

找最大用小堆，找最小用大堆，找中间用两个堆。

这道题用小堆，新元素插入的时候就替换根元素，然后重新构造小堆，构造完成后的根元素就是第 K 大的元素，不论要处理的元素有多少以及是否固定，小堆的长度都固定为 K ，且根元素就是第 K 大的元素。

只有比根元素大的才让进入堆。

这里使用 PriorityQueue 优先队列。

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        if (k > nums.length) {
            return -1;
        }
        int len = nums.length;
        // 大小为 k ，排序规则为降序
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, (a, b) -> a - b);
        for (int i = 0; i < k; i++) {
            minHeap.add(nums[i]);
        }
        for (int i = k; i < len; i++) {
            Integer topEle = minHeap.peek();
            if (nums[i] > topEle) {
                minHeap.poll();
                minHeap.offer(nums[i);
            }
        }
        return minHeap.peek();
    }
}

2.合并 K 个排序链表

原题：力扣23.

public ListNode mergeKLists(ListNode[] lists) {
	if (lists == null || lists.length == 0) {
        return null;
    }
    PriorityQueue<ListNode> q = new PriorityQueue<>(Comparator.comparing(node -> node.val));
    for (int i = 0; i < lists.length; i++) {
        if (lists[i] != null) {
            q.add(lists[i]);
        }
    }
    ListNode dummy = new ListNode(0);
    ListNode tail = dummy;

    while (!q.isEmpty()) {
        tail.next = q.poll();
        tail = tail.next;
        if (tail.next != null) {
            q.add(tail.next);
        }
    }
    return dummy.next;
}