首页 > 其他分享 >优先级队列的应用 I

优先级队列的应用 I

时间:2024-01-29 15:58:23浏览次数:34  
标签:优先级 队列 元素 中位数 large 应用 small 2.1 MedianFinder

目录

1. 题目列表

题目列表:

序号 题目 难度
1 295. 数据流的中位数 困难

2. 应用

2.1. Leetcode 295. 数据流的中位数

2.1.1. 题目

295. 数据流的中位数

中位数是有序整数列表中的中间值。如果列表的大小是偶数,则没有中间值,中位数是两个中间值的平均值。

  • 例如 arr = [2,3,4] 的中位数是 3 。
  • 例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。
    实现 MedianFinder 类:
  • MedianFinder() 初始化 MedianFinder 对象。
  • void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
  • double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。

示例 1:

输入
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
输出
[null, null, null, 1.5, null, 2.0]
解释
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1); // arr = [1]
medianFinder.addNum(2); // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3); // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

2.1.2. 解题思路

我们可以考虑维护两个优先队列:

  • small:维护一个大根堆用于保存较小的元素,其中,堆顶的元素最大;

  • large:维护一个小根堆用于保存较大的元素,其中,堆顶的元素最小。

image

假设添加的元素个数为 \(n\),如果 \(n\) 为奇数,我们保持 \(small\) 和 \(large\) 中的元素个数分别为 \(\frac{n}{2} + 1\)、\(\frac{n}{2}\),这样,\(small\) 中多的元素,就是中位数。

如果 \(n\) 为偶数,那么,中位数就是两个堆的堆顶元素的平均值。

当我们尝试添加一个元素 \(num\) 的时候,如果其中一个堆中的元素较多,可以将元素 \(num\) 放入该堆,然后再将堆顶的元素,放入另一个堆中。

2.1.3. 代码实现

class MedianFinder {
    private PriorityQueue<Integer> small; // 大根堆,保存较小的元素
    private PriorityQueue<Integer> large; // 小根堆,保存较大的元素

    public MedianFinder() {
        small = new PriorityQueue<>((a, b) -> a - b);
        large = new PriorityQueue<>((a, b) -> b - a);
    }

    public void addNum(int num) {
        if (small.size() >= large.size()) {
            small.offer(num);
            large.offer(small.poll());
        } else {
            large.offer(num);
            small.offer(large.poll());
        }
    }

    public double findMedian() {
        if (large.size() < small.size()) {
            return small.peek();
        } else if (large.size() > small.size()) {
            return large.peek();
        } else {
            return (small.peek() + large.peek()) / 2.0;
        }
    }
}

参考:

标签:优先级,队列,元素,中位数,large,应用,small,2.1,MedianFinder
From: https://www.cnblogs.com/larry1024/p/17994557

相关文章

  • 振弦采集仪在工程监测中的应用研究
    振弦采集仪在工程监测中的应用研究振弦采集仪是一种用于监测结构物振动状况的设备,通过采集结构物表面的振弦信号,并进行分析处理,可以获得结构的动态响应信息。在工程监测中,振弦采集仪具有广泛的应用研究。 首先,振弦采集仪可以用于结构物的结构健康监测。通过监测结构物表面的......
  • Fortify Static Code Analyzer 23.2 for macOS, Linux & Windows - 静态应用安全测试
    FortifyStaticCodeAnalyzer23.2formacOS,Linux&Windows-静态应用安全测试FortifySCA-代码漏洞扫描工具|静态代码测试|代码安全分析请访问原文链接:https://sysin.org/blog/fortify-static-code-analyzer/,查看最新版。原创作品,转载请保留出处。作者主页:sysin.o......
  • 振弦采集仪在工程监测中的应用研究
    振弦采集仪在工程监测中的应用研究振弦采集仪是一种用于监测结构物振动状况的设备,通过采集结构物表面的振弦信号,并进行分析处理,可以获得结构的动态响应信息。在工程监测中,振弦采集仪具有广泛的应用研究。首先,振弦采集仪可以用于结构物的结构健康监测。通过监测结构物表面的振弦信......
  • 通过LINUX驱动控制FPGA端PWM外设(LED) 通过应用程序命令传参随意修改寄存器的值(PWM波频
    用法:先下发下面的命令让kernel信息打印到串口:echo7417>/proc/sys/kernel/printk然后增加程序可执行性:chmod777pwmdriver_app  先执行./pwmdriver_app/dev/pwm400000200然后执行./pwm_driver_app/dev/pwm400000200,可以发现LED[1]......
  • 隐写术-数字水印的原理、实现及应用
    导语前段时间有一则阿里员工外泄信息被捕获的报道。大致内容是阿里的某位员工,在内部办公软件截图,使用PS工具修掉截图上的可见水印,然后传播出去,但阿里通过图片携带的不可见水印,解读了截图员工的员工编码,从而找到了泄漏图片的员工。一时间,图片的盲水印技术受到了广泛关注。本文针对......
  • 天拓四方:TDE物联网智能采集终端在智能工业领域的应用
    随着物联网技术的快速发展,物联网设备产生的数据量呈指数级增长,如何有效地采集、处理和分析这些数据成为了一个重要的问题。物联网智能采集终端作为一种高效、实时的数据采集工具,具有强大的数据采集、处理和分析能力,能够满足各种物联网应用的需求。TDE物联网智能采集终端的特点TDE......
  • 《基于“源启+”的应用重构白皮书》
      当前,行业数字化转型驶入“深水区”,全新的市场竞争格局对行业发展提出更高的要求,企业高质量发展需要借助新架构新应用重新定义数字生产力,重塑商业模式与市场核心竞争力。 在中国电子主办,中电金信承办的“数字原生·向新而行——数字金融开放创新与架构转型发展论坛”上,来......
  • LangChain大模型应用开发指南:从基础链式结构到ReAct对话解构
    在自然语言处理领域,大模型的应用已经成为了一种趋势。LangChain是一个基于深度学习的自然语言处理框架,它通过使用链式结构和ReAct对话模型,为开发者提供了一种高效、灵活的方式来进行大模型应用开发。本指南将介绍如何从基础链式结构开始,逐步构建ReAct对话解构,以实现自然语言处理应......
  • iOS应用崩溃了,如何通过崩溃手机连接电脑查找日志方法
    ​在iOS应用开发过程中,调试日志和奔溃日志是开发者必不可少的工具。当iOS手机崩溃时,我们可以连接电脑并使用XcodeConsole等工具来查看日志。然而,这种方式可能不够方便,并且处理奔溃日志也相当繁琐。克魔助手的出现为开发者带来了极大的便利,本文将详细介绍其功能和使用方法。克魔......
  • 电力监控系统在办公楼建筑电力运行和节能中的应用
    【摘要】本文中概述电力监控系统结构和作用,通过列举工程实例,详细介绍了电力监控系统在民用建筑电力系统运行和节能中的应用,以及在推广和发展方面需要改进的问题。【关键词】民用建筑;电力监控系统;运行和节能中的应用引言随着国民经济的不断增强,城镇建设速度不断加快,智能建筑已经从发......