博客

设计一个找到数据流中第K大元素的类（class）。注意是排序后的第K大元素，不是第K个不同的元素。

你的 KthLargest 类需要一个同时接收整数 k 和整数数组nums 的构造器，它包含数据流中的初始元素。每次调用 KthLargest.add，返回当前数据流中第K大的元素。

解法一：记录前K个的最大值：每次进来一个比K个值里面最小值大的数，踢出K个值里面最小的那个数，把最新的那个数记录进K个值里面（先排序，使用快排），快排的时间复杂度是KlogK，有k个值，所以该解法的复杂度为O（N*K（logK））

解法二：使用优先队列（priorityQueue）维持一个小顶堆（min heap）

java中的优先队列，priorityQueue的作用是保证每次取出的元素都是队列中权值最小的。其通过

堆

实现，具体说是通过完全二叉树（complete binary tree）实现的

小顶堆

（任意一个非叶子节点的权值，都不大于其左右子节点的权值）

class KthLargest {
    final PriorityQueue<Integer> pq;
    final int k;
    
    public KthLargest(int k, int[] nums) {
        this.k = k;
        pq = new PriorityQueue<>(k);

        for(int i : nums){//对传进来的int数组遍历
            add(i);
        }
    }
    
    public int add(int val) {
        if(pq.size() < k)//如果队列中的数量少于K，直接添加入优先队列，优先队列会自动维持小顶堆
            pq.offer(val);
        else{
            if(pq.peek() < val){//否则队列中的数量大于或者等于K，优先队列中的最小数字小于新的数据，优先队列中的顶堆要被移除，并且添加入新的数据进优先队列
                pq.poll();
                pq.offer(val);

            }        

        }
        return pq.peek();//返回当前第K大的数

    }
}

维持小顶堆的时间复杂度是

,遍历的有N个数据，所以时间复杂度为O(Nlog2K)