【懒删除堆】力扣2349. 设计数字容器系统

设计一个数字容器系统,可以实现以下功能:

在系统中给定下标处 插入 或者 替换 一个数字。
返回 系统中给定数字的最小下标。
请你实现一个 NumberContainers 类:

NumberContainers() 初始化数字容器系统。
void change(int index, int number) 在下标 index 处填入 number 。如果该下标 index 处已经有数字了,那么用 number 替换该数字。
int find(int number) 返回给定数字 number 在系统中的最小下标。如果系统中没有 number ,那么返回 -1 。

示例:
输入:
[“NumberContainers”, “find”, “change”, “change”, “change”, “change”, “find”, “change”, “find”]
[[], [10], [2, 10], [1, 10], [3, 10], [5, 10], [10], [1, 20], [10]]
输出:
[null, -1, null, null, null, null, 1, null, 2]

解释:
NumberContainers nc = new NumberContainers();
nc.find(10); // 没有数字 10 ,所以返回 -1 。
nc.change(2, 10); // 容器中下标为 2 处填入数字 10 。
nc.change(1, 10); // 容器中下标为 1 处填入数字 10 。
nc.change(3, 10); // 容器中下标为 3 处填入数字 10 。
nc.change(5, 10); // 容器中下标为 5 处填入数字 10 。
nc.find(10); // 数字 10 所在的下标为 1 ,2 ,3 和 5 。因为最小下标为 1 ,所以返回 1 。
nc.change(1, 20); // 容器中下标为 1 处填入数字 20 。注意,下标 1 处之前为 10 ,现在被替换为 20 。
nc.find(10); // 数字 10 所在下标为 2 ,3 和 5 。最小下标为 2 ,所以返回 2 。

在这里插入图片描述

懒删除堆

class NumberContainers {unordered_map<int, int> m;unordered_map<int, priority_queue<int, vector<int>, greater<int>>> ms;
public:NumberContainers() {}void change(int index, int number) {m[index] = number;ms[number].push(index);}int find(int number) {auto it = ms.find(number);if(it == ms.end()) return -1;auto &q = it -> second;while(!q.empty() && m[q.top()] != number) q.pop();return q.empty() ? -1 : q.top();}
};

我们可以建立一个哈希表m用来储存最新的index存放的是哪个number。我们再建立一个哈希表ms,键用来储存number,然后值用一个最小堆来储存index。最小堆实际上就是我们需要的最小索引,但是由于可能最小堆里的数值的索引可能被替换掉,所以我们要进行检查。当m[q.top()] != number的时候,说明该索引已经被替换成其他值,所以我们就将最小堆堆顶元素弹出,最后满足m[q.top()] = number的堆顶元素就是代码中构造的find函数的返回值。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/10205.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

利用飞书机器人进行 - ArXiv自动化检索推荐

相关作者的Github仓库 ArXivToday-Lark 使用教程 Step1 新建机器人 根据飞书官方机器人使用手册&#xff0c;新建自定义机器人&#xff0c;并记录好webhook地址&#xff0c;后续将在配置文件中更新该地址。 可以先完成到后续步骤之前&#xff0c;后续的步骤与安全相关&…

SpringBoot 日志

目录 一. 日志概述 二. 日志的使用 1. 打印日志 (1) 获取日志对象 (2) 输出要打印的内容 2. 日志框架简介 (1) 门面模式简介 (2) SLF4J 框架简介 3. 日志的格式 4. 日志的级别 5. 日志配置 (1) 配置日志级别 (2) 日志持久化存储 ① 配置日志文件名 ② 配置日志的…

RK3568中使用QT opencv(显示基础图像)

文章目录 一、查看对应的开发环境是否有opencv的库二、QT使用opencv 一、查看对应的开发环境是否有opencv的库 在开发板中的/usr/lib目录下查看是否有opencv的库&#xff1a; 这里使用的是正点原子的ubuntu虚拟机&#xff0c;在他的虚拟机里面已经安装好了opencv的库。 二、…

LMI Gocator GO_SDK VS2019引用配置

LMI SDK在VS2019中的引用是真的坑爹,总结一下经验,希望后来的人能少走弯路.大致内容如下: &#xff08;1&#xff09; 环境变量 &#xff08;2&#xff09;C/C 附加包含目录 E:\GWQ\Gocator\GO_SDK\Gocator\GoSdk E:\GWQ\Gocator\GO_SDK\Platform\kApi &#xff08;3&#…

模型I/O

文章目录 什么是模型I/O模型I/O功能之输出解析器输出解析器的功能输出解析器的使用Pydantic JSON输出解析器结构化输出解析器 什么是模型I/O 模型I/O在所有LLM应用中&#xff0c;核心元素无疑都是模型本身。与模型进行有效的交互是实现高效、灵活和可扩展应用的关键。LangChain…

C语言练习(31)

有5个学生&#xff0c;每个学生有3门课程的成绩&#xff0c;从键盘输入以上数据&#xff08;包括学号、姓名、3门课程成绩&#xff09;&#xff0c;计算出平均成绩&#xff0c;将原有数据和计算出的平均分数存放在磁盘文件stud中。 设5名学生的学号、姓名和3门课程成绩如下&am…

【Block总结】DynamicFilter,动态滤波器降低计算复杂度,替换传统的MHSA|即插即用

论文信息 标题: FFT-based Dynamic Token Mixer for Vision 论文链接: https://arxiv.org/pdf/2303.03932 关键词: 深度学习、计算机视觉、对象检测、分割 GitHub链接: https://github.com/okojoalg/dfformer 创新点 本论文提出了一种新的标记混合器&#xff08;token mix…

「AI学习笔记」深度学习的起源与发展:从神经网络到大数据(二)

深度学习&#xff08;DL&#xff09;是现代人工智能&#xff08;AI&#xff09;的核心之一&#xff0c;但它并不是一夜之间出现的技术。从最初的理论提出到如今的广泛应用&#xff0c;深度学习经历了几乎一个世纪的不断探索与发展。今天&#xff0c;我们一起回顾深度学习的历史…

Axure PR 9 旋转效果 设计交互

大家好&#xff0c;我是大明同学。 这期内容&#xff0c;我们将学习Axure中的旋转效果设计与交互技巧。 旋转 创建旋转效果所需的元件 1.打开一个新的 RP 文件并在画布上打开 Page 1。 2.在元件库中拖出一个按钮元件。 创建交互 创建按钮交互状态 1.选中按钮元件&#xf…

【外文原版书阅读】《机器学习前置知识》2.用看电影推荐的例子带你深入了解向量点积在机器学习的作用

目录 3.3 Where Are You Looking, Vector? The Dot Product 个人主页&#xff1a;Icomi 大家好&#xff0c;我是Icomi&#xff0c;本专栏是我阅读外文原版书《Before Machine Learning》对于文章中我认为能够增进线性代数与机器学习之间的理解的内容的一个输出&#xff0c;希望…

论文阅读(八):结构方程模型用于研究数量遗传学中的因果表型网络

1.论文链接&#xff1a;Structural Equation Models for Studying Causal Phenotype Networks in Quantitative Genetics 摘要&#xff1a; 表型性状可能在它们之间发挥因果作用。例如&#xff0c;农业物种的高产可能会增加某些疾病的易感性&#xff0c;相反&#xff0c;疾病的…

每日一题——序列化二叉树

序列化二叉树 BM39 序列化二叉树题目描述序列化反序列化 示例示例1示例2 解题思路序列化过程反序列化过程 代码实现代码说明复杂度分析总结 BM39 序列化二叉树 题目描述 请实现两个函数&#xff0c;分别用来序列化和反序列化二叉树。二叉树的序列化是将二叉树按照某种遍历方式…

JVM_程序计数器的作用、特点、线程私有、本地方法的概述

①. 程序计数器 ①. 作用 (是用来存储指向下一条指令的地址,也即将要执行的指令代码。由执行引擎读取下一条指令) ②. 特点(是线程私有的 、不会存在内存溢出) ③. 注意:在物理上实现程序计数器是在寄存器实现的,整个cpu中最快的一个执行单元 ④. 它是唯一一个在java虚拟机规…

Attention--人工智能领域的核心技术

1. Attention 的全称与基本概念 在人工智能&#xff08;Artificial Intelligence&#xff0c;AI&#xff09;领域&#xff0c;Attention 机制的全称是 Attention Mechanism&#xff08;注意力机制&#xff09;。它是一种能够动态分配计算资源&#xff0c;使模型在处理输入数据…

机器学习2 (笔记)(朴素贝叶斯,集成学习,KNN和matlab运用)

朴素贝叶斯模型 贝叶斯定理&#xff1a; 常见类型 算法流程 优缺点 集成学习算法 基本原理 常见方法 KNN&#xff08;聚类模型&#xff09; 算法性质&#xff1a; 核心原理&#xff1a; 算法流程 优缺点 matlab中的运用 朴素贝叶斯模型 朴素贝叶斯模型是基于贝叶斯…

智慧园区系统助力企业智能化升级实现管理效率与安全性全方位提升

内容概要 在当今数字化转型的浪潮中&#xff0c;企业面临着前所未有的挑战和机遇。智慧园区系统作为一种创新性解决方案&#xff0c;正在快速崛起&#xff0c;帮助企业实现全面的智能化升级。这套系统不仅仅是一个简单的软件工具&#xff0c;而是一个强大的综合管理平台&#…

【视频+图文详解】HTML基础4-html标签的基本使用

图文教程 html标签的基本使用 无序列表 作用&#xff1a;定义一个没有顺序的列表结构 由两个标签组成&#xff1a;<ul>以及<li>&#xff08;两个标签都属于容器级标签&#xff0c;其中ul只能嵌套li标签&#xff0c;但li标签能嵌套任何标签&#xff0c;甚至ul标…

电子电气架构 --- 在智能座舱基础上定义人机交互

我是穿拖鞋的汉子&#xff0c;魔都中坚持长期主义的汽车电子工程师。 老规矩&#xff0c;分享一段喜欢的文字&#xff0c;避免自己成为高知识低文化的工程师&#xff1a; 简单&#xff0c;单纯&#xff0c;喜欢独处&#xff0c;独来独往&#xff0c;不易合同频过着接地气的生活…

SAP SD学习笔记27 - 请求计划(开票计划)之1 - 定期请求

上两章讲了贩卖契约&#xff08;框架协议&#xff09;的概要&#xff0c;以及贩卖契约中最为常用的 基本契约 - 数量契约和金额契约。 SAP SD学习笔记26 - 贩卖契约(框架协议)的概要&#xff0c;基本契约 - 数量契约_sap 框架协议-CSDN博客 SAP SD学习笔记27 - 贩卖契约(框架…

Ansible自动化运维实战--fetch、cron和group模块(5/8)

文章目录 一、fetch 模块1.1、功能1.2、常用参数1.3、测试1.4、注意事项 二、cron 模块2.1、功能2.2、常用参数2.3、注意事项 三、group模块3.1、功能3.2、常用参数3.3、例子3.4、注意事项 一、fetch 模块 1.1、功能 fetch 模块的主要功能是将远程主机上的文件复制到本地控制…