703. 数据流中的第K大元素

栏目: Java · 发布时间: 7年前

内容简介:版权声明: 本文为博主原创文章,发表自知一的指纹。转载需向设计一个找到数据流中第K大元素的类(class)。注意是排序后的第K大元素,不是第K个不同的元素。你的 KthLargest 类需要一个同时接收整数 k 和整数数组nums 的构造器,它包含数据流中的初始元素。每次调用 KthLargest.add,返回当前数据流中第K大的元素。

版权声明: 本文为博主原创文章,发表自知一的指纹。转载需向 我的邮箱 申请。

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

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

import java.util.PriorityQueue;

public class KthLargest {
    private PriorityQueue<Integer> minHeap;
    private int kSize;

    public KthLargest(int k, int[] nums) {
        kSize = k;
        minHeap=new PriorityQueue<Integer>(kSize);
        for (int i = 0; i< nums.length; i++){
            add(nums[i]);
        }
    }

    public int add(int val) {
        if (minHeap.size() < kSize){
            minHeap.offer(val);
        }else if (minHeap.peek() < val){
            minHeap.poll();
            minHeap.offer(val);
        }
        return minHeap.peek();
    }
}

Java中PriorityQueue通过二叉小顶堆实现,可以用一棵完全二叉树表示。

关于堆操作: https://shmilyaw-hotmail-com.iteye.com/blog/1775868

操作说明:

方法名 功能描述
add(Ee) 在队列头部增加一个元素,如果容量已满,则抛出异常,成功则返回true。
clear() 清空
contains(Objecto) 检查是否包含当前参数元素
offer(Ee) 在队列头部增加一个元素,如果容量已满,则返回false,成功加入,返回true。
peek() 返回队列头部节点,但不移除队列头节点。
poll() 将队列头部元素移出队列并返回。
remove(Objecto) 将队列头部元素移出队列并返回,如果队列为空,则抛出异常。
size() 返回长度

如果此文章能给您带来小小的提升,不妨小额赞赏我一下,以鼓励我写出更好的文章!

703. 数据流中的第K大元素

微信打赏

703. 数据流中的第K大元素

支付宝打赏


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。

ACM/ICPC程序设计与分析

ACM/ICPC程序设计与分析

沈云付 / 清华大学 / 2010-7 / 39.50元

《ACM/ICPC程序设计与分析(C++实现)》介绍ACM国际大学生程序设计竞赛概况及程序设计基础,系统介绍数论、组合数学、动态规划、计算几何、搜索、图论和网络流等专题的典型算法,挑选历年竞赛中许多有代表性的竞赛题作为例题进行分析,便于学生编程时模仿学习。每章的例题和习题都配有输入输出样例,方便学生在编程时测试与调试程序。《ACM/ICPC程序设计与分析(C++实现)》以C++为程序设计语言,以提......一起来看看 《ACM/ICPC程序设计与分析》 这本书的介绍吧!

在线进制转换器
在线进制转换器

各进制数互转换器

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器

html转js在线工具
html转js在线工具

html转js在线工具