LeetCode刷题之路703题数据流中的第K大元素

题目链接

https://leetcode-cn.com/problems/kth-largest-element-in-a-stream/文章源自随机的未知-https://sjdwz.com/11125.html

题目内容

设计一个找到数据流中第K大元素的类（class）。注意是排序后的第K大元素，不是第K个不同的元素。
你的 KthLargest 类需要一个同时接收整数 k 和整数数组nums 的构造器，它包含数据流中的初始元素。每次调用 KthLargest.add，返回当前数据流中第K大的元素。文章源自随机的未知-https://sjdwz.com/11125.html

示例:文章源自随机的未知-https://sjdwz.com/11125.html

int k = 3;
int[] arr = [4,5,8,2];
KthLargest kthLargest = new KthLargest(3, arr);
kthLargest.add(3); // returns 4
kthLargest.add(5); // returns 5
kthLargest.add(10); // returns 5
kthLargest.add(9); // returns 8
kthLargest.add(4); // returns 8文章源自随机的未知-https://sjdwz.com/11125.html

分析

可以使用小顶堆的方式来进行求解；
分析如下：
1、首先建立一个大小为k的小顶堆；
2、如果元素比堆顶元素小，直接排除；
3、如果元素比堆顶元素大，剔除顶堆元素，重新调整堆，返回堆顶元素。文章源自随机的未知-https://sjdwz.com/11125.html

代码

import java.util.PriorityQueue;

class KthLargest {

    private PriorityQueue<Integer> pri_queue;
    private int k;
    public KthLargest(int k, int[] nums) {
        //将k赋值给类的全局变量
        this.k = k;
        //创建一个大小为k的优先队列
        pri_queue = new PriorityQueue<>(k);
        for(int val : nums){
            add(val);
        }
    }

    public int add(int val) {
        //如果pri_queue没有满
        if(pri_queue.size()<k){
            //直接将val加入队列，并调整
            pri_queue.offer(val);
        }
        //如果堆顶元素小于val
        else if(pri_queue.peek() < val){
            //弹出堆顶元素
            pri_queue.poll();
            //加入val并调整
            pri_queue.offer(val);
        }

        //返回堆顶元素
        return pri_queue.peek();
    }
}

/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest obj = new KthLargest(k, nums);
 * int param_1 = obj.add(val);
 */

欢迎关注

欢迎大家的关注文章源自随机的未知-https://sjdwz.com/11125.html

扫描下方的二维码关注我的微信公众号：随机的未知
文章源自随机的未知-https://sjdwz.com/11125.html