【数据结构与算法 | 堆篇】力扣215

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 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 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();
    }
}