[Leetcode 703]流中第K个最大元素Kth Largest Element in a Stream优先队列

题目

找到一串数字中的第K大元素

在原数组的基础上,每次会不断插入元素

插入的同时要返回插入后第K大的元素

https://leetcode.com/problems/kth-largest-element-in-a-stream/

Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Implement KthLargest class:

  • KthLargest(int k, int[] nums) Initializes the object with the integer k and the stream of integers nums.
  • int add(int val) Appends the integer val to the stream and returns the element representing the kth largest element in the stream.

 

Example 1:

Input
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
Output
[null, 4, 5, 5, 8, 8]

Explanation
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

 

 

思路

tips区别

优先队列:根据自定义的优先级(更大/更小/甚至字母abc),按照优先级大的先出

普通队列:严格的先进先出

example:https://www.liaoxuefeng.com/wiki/1252599548343744/1265120632401152

优先队列经常用在dijsktra迪杰斯特拉算法,最小堆。这题先熟悉优先队列


q=new PriorityQueue<>(k);

经过定义后,q.peek()返回的则是第K大

 

找第K大的元素,即只用管大元素,小元素的顺序不用管

即每次add,

如果add的元素<第K大,那他进不进队列,对第K大都没有影响,直接忽略掉,return peek;

如果add的元素>第K大,则poll/remove排出队列中最小的,offer/add进该元素,更新队列,再return peek

 

代码

class KthLargest {
    PriorityQueue<Integer> q;
    int k;

    public KthLargest(int k, int[] nums) {
        this.k=k;
        q=new PriorityQueue<>(k);//定义返回第K大的数
        for(int n:nums){
            add(n);
        }
    }

    public int add(int val) {
        if(q.size()<k){
            //初始化
            q.offer(val);
        }
        else if(q.peek()<val){
            //只有当加入的值大于第K大时,才更新队列
            q.poll();
            q.offer(val);
        }
        //返回第K大
        return q.peek();
    }
}

 

   
上一篇:实验3 转移指令跳转原理及其简单应用编程


下一篇:Day_26 【Java基础】Stream API 与 Optional类【附源码】