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

2020年2月5日09:01:14算法 LeetCode评论26阅读模式

题目链接

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

扫描下方的二维码关注我的微信公众号:随机的未知
LeetCode刷题之路703题数据流中的第K大元素文章源自随机的未知-https://sjdwz.com/11125.html

文章源自随机的未知-https://sjdwz.com/11125.html
欢迎关注本站微信公众号:随机的未知 如果喜欢本文,欢迎点赞,收藏,转发,打赏。
  • 本文由 发表于 2020年2月5日09:01:14
  • 转载请注明:来源:随机的未知 本文链接https://sjdwz.com/11125.html
算法

详解堆排序

什么是堆 堆首先是一个完全二叉树,堆分为大顶堆和小顶堆; 大顶堆 : 每个节点的值大于或等于其左右孩子节点的值,称为大顶堆。 小顶堆同理就是每个节点的值小于或等于其左右孩子节点的值。 注意: 每个节点...
算法

详解基数排序

基本思想 基数排序的思想是将整数按位数切割成不同的数字,然后按每个位数分别比较从而得到有序的序列。 例子 本文以数组中元素均为正整数来演示思想。 给定一个数组 arr = < 6, 56, 89 , ...
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定