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

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

内容简介：版权声明：本文为博主原创文章，发表自知一的指纹。转载需向设计一个找到数据流中第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()	返回长度

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

微信打赏

支付宝打赏

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

查看所有标签

猜你喜欢:

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

码农书籍

MySQL性能调优与架构设计

简朝阳 / 2009-6 / 59.80元

《MySQL性能调优与架构设计》以 MySQL 数据库的基础及维护为切入点，重点介绍了 MySQL 数据库应用系统的性能调优，以及高可用可扩展的架构设计。全书共分3篇，基础篇介绍了MySQL软件的基础知识、架构组成、存储引擎、安全管理及基本的备份恢复知识。性能优化篇从影响 MySQL 数据库应用系统性能的因素开始，针对性地对各个影响因素进行调优分析。如 MySQL Schema 设计的技巧......一起来看看《MySQL性能调优与架构设计》这本书的介绍吧!

码农工具

CSS 压缩/解压工具

在线压缩/解压 CSS 代码

随机密码生成器

多种字符组合密码