当前位置: 首页 > news >正文

【数据结构和算法】无限集中的最小数字

其他系列文章导航

Java基础合集

设计模式合集

多线程合集

分布式合集

ES合集


文章目录

其他系列文章导航

文章目录

前言

一、题目描述

二、题解

三、代码

四、总结


前言

这是力扣的2336题,难度为中等,解题方案有很多种,本文讲解我认为最奇妙的一种。


一、题目描述

现有一个包含所有正整数的集合 [1, 2, 3, 4, 5, ...] 。

实现 SmallestInfiniteSet 类:

  • SmallestInfiniteSet() 初始化 SmallestInfiniteSet 对象以包含 所有 正整数。
  • int popSmallest() 移除 并返回该无限集中的最小整数。
  • void addBack(int num) 如果正整数 num  存在于无限集中,则将一个 num 添加 到该无限集中。

示例:

输入
["SmallestInfiniteSet", "addBack", "popSmallest", "popSmallest", "popSmallest", "addBack", "popSmallest", "popSmallest", "popSmallest"]
[[], [2], [], [], [], [1], [], [], []]
输出
[null, null, 1, 2, 3, null, 1, 4, 5]解释
SmallestInfiniteSet smallestInfiniteSet = new SmallestInfiniteSet();
smallestInfiniteSet.addBack(2);    // 2 已经在集合中,所以不做任何变更。
smallestInfiniteSet.popSmallest(); // 返回 1 ,因为 1 是最小的整数,并将其从集合中移除。
smallestInfiniteSet.popSmallest(); // 返回 2 ,并将其从集合中移除。
smallestInfiniteSet.popSmallest(); // 返回 3 ,并将其从集合中移除。
smallestInfiniteSet.addBack(1);    // 将 1 添加到该集合中。
smallestInfiniteSet.popSmallest(); // 返回 1 ,因为 1 在上一步中被添加到集合中,// 且 1 是最小的整数,并将其从集合中移除。
smallestInfiniteSet.popSmallest(); // 返回 4 ,并将其从集合中移除。
smallestInfiniteSet.popSmallest(); // 返回 5 ,并将其从集合中移除。

提示:

  • 1 <= num <= 1000
  • 最多调用 popSmallest 和 addBack 方法 共计 1000 次

二、题解

这题的关键点是始终要保证无限集合是连续的。无限集合的范围可以认为是从 1 到正无穷大,并且都是正整数。

这道我是用TreeSet和一个min变量来维护这个无限集合。为什么用TreeSet,因为TreeSet支持维护元素的自然顺序。

TreeSet:小于min的有序集合。

min:有序集合的最小值。

添加元素的时候分为两种情况:

  1. 添加元素的时候如果添加的值大于等于无限集合中的最小值 min ,就不要添加,因为无限集合是连续的,添加的元素在无限集合中已经存在。(简单点说:比min还大的数不用加,说明已经存在了)

  2. 添加的元素如果小于无限集合的最小值 min 也不能直接添加,如果贸然添加会导致无限集合不连续,只需要把它添加到有序集合 TreeSet 中即可, TreeSet 中存放的值都是小于 min 的。所以要加在TreeSet中,要靠TreeSet来维护。

删除元素的时候:

  1. 删除的时候先判断有序集合 TreeSet 是否为空,如果不为空,说明存在比 min 还小的元素,直接从 TreeSet 中删除。否则就从有序集合中删除 min ,删除之后 min 值要加 1 。


三、代码

class SmallestInfiniteSet {TreeSet<Integer> set = new TreeSet<>();int min = 1;public SmallestInfiniteSet() {}public int popSmallest() {if (set.isEmpty()) {return min++;//先返回,再++}return set.pollFirst();//弹出set的第一个元素,并删除}public void addBack(int num) {if (num < min) {//大于的话,说明存在了set.add(num);}}
}

四、总结

使用TreeSet和min变量来维护一个无限集合,保证集合的连续性。添加元素时,若元素大于等于min,则不添加;若元素小于min,则将其添加到TreeSet中。删除元素时,先判断TreeSet是否为空,若不为空,则从TreeSet中删除元素;若为空,则将min值加1。该算法能够高效地添加和删除元素,并保持集合的连续性。

该算法还可以用优先队列(小根堆)+ hash表解题,比较优秀。


相关文章:

【数据结构和算法】无限集中的最小数字

其他系列文章导航 Java基础合集 设计模式合集 多线程合集 分布式合集 ES合集 文章目录 其他系列文章导航 文章目录 前言 一、题目描述 二、题解 三、代码 四、总结 前言 这是力扣的2336题&#xff0c;难度为中等&#xff0c;解题方案有很多种&#xff0c;本文讲解我认为…...

SimpleDataFormat 非线程安全

目录 前言 正文 1.出现异常 2.解决方法1 3.解决方法2 总结 前言 SimpleDateFormat 类是 Java 中处理日期和时间格式化和解析的类&#xff0c;但它并不是线程安全的。这意味着多个线程不能安全地共享一个 SimpleDateFormat 实例进行日期和时间的解析和格式化。当多个…...

SpringBoot : ch12 多模块配置YAML文件

前言 当您使用SpringBoot框架进行项目开发时&#xff0c;通常需要配置一些参数和属性。在实际开发中&#xff0c;可能需要将这些配置参数分成多个不同的YAML文件&#xff0c;并将它们组织到不同的模块中。这样可以方便管理和维护配置文件&#xff0c;并且可以避免配置文件的冲…...

TensorRT之LeNet5部署(onnx方式)

文章目录 前言LeNet-5部署1.ONNX文件导出2.TensorRT构建阶段(TensorRT模型文件)&#x1f9c1;创建Builder&#x1f367;创建Network&#x1f36d;使用onnxparser构建网络&#x1f36c;优化网络&#x1f361;序列化模型&#x1f369;释放资源 3.TensorRT运行时阶段(推理)&#x…...

Xilinx FPGA平台DDR3设计详解(二):DDR SDRAM组成与工作过程

本文主要介绍一下DDR SDRAM的基本组成以及工作过程&#xff0c;方便大家更好的理解和掌握DDR的控制与读写。 一、DDR SDRAM的基本组成 1、SDRAM的基本单元 SDRAM的基本单元是一个CMOS晶体管和一个电容组成的电路。 晶体管最上面的一端&#xff0c;称作栅极&#xff0c;通过…...

ios(swiftui) 属性包装器详解

目录 1. State 2. Binding 3. ObservedObject 和Published 4. StateObject 5. EnvironmentObject和Environment 6. AppStorage 在 SwiftUI 中&#xff0c;属性包装器用于增强和管理视图的状态&#xff0c;以及处理视图与数据模型之间的绑定和交互。下面是一些常见…...

【智能家居】面向对象编程OOP和设计模式(工厂模式)

面向对象编程 类和对象 面向对象编程和面向过程编程区别 设计模式 软件设计模式按类型分 工厂模式 面向对象编程 面向对象编程&#xff08;Object-Oriented Programming&#xff0c;OOP&#xff09;是一种程序设计范式&#xff0c;其中程序被组织成对象的集合&#xff0c;每…...

Docker安装Memcached+Python调用

简介&#xff1a;Memcached是一个通用的分布式内存缓存系统。它通常用于通过在RAM中缓存数据和对象来加速动态数据库驱动的网站&#xff0c;以减少必须读取外部数据源&#xff08;如数据库或API&#xff09;的次数。Memcached的API提供了一个分布在多台机器上的非常大的哈希表。…...

网页开发 HTML

目录 HTML概述 HTML结构 HTML标签语法 基本标签 标题标签 换行标签 段落标签 文本格式化标签 特殊符号 div和span标签 超链接标签 锚点 img标签 列表标签 表格标签 表单标签 HTML概述 HTML&#xff0c;即超文本标记语言&#xff08;HyperText Markup Language …...

SHAP(五):使用 XGBoost 进行人口普查收入分类

SHAP&#xff08;五&#xff09;&#xff1a;使用 XGBoost 进行人口普查收入分类 本笔记本演示了如何使用 XGBoost 预测个人年收入超过 5 万美元的概率。 它使用标准 UCI 成人收入数据集。 要下载此笔记本的副本&#xff0c;请访问 github。 XGBoost 等梯度增强机方法对于具有…...

LeetCode 8 字符串转整数

题目描述 字符串转换整数 (atoi) 请你来实现一个 myAtoi(string s) 函数&#xff0c;使其能将字符串转换成一个 32 位有符号整数&#xff08;类似 C/C 中的 atoi 函数&#xff09;。 函数 myAtoi(string s) 的算法如下&#xff1a; 读入字符串并丢弃无用的前导空格检查下一…...

前缀和 LeetCode1423. 可获得的最大点数

几张卡牌 排成一行&#xff0c;每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。 每次行动&#xff0c;你可以从行的开头或者末尾拿一张卡牌&#xff0c;最终你必须正好拿 k 张卡牌。 你的点数就是你拿到手中的所有卡牌的点数之和。 给你一个整数数组 cardPoi…...

探索意义的深度:自然语言处理中的语义相似性

一、说明 语义相似度&#xff0c;反应出计算机对相同内容&#xff0c;不同表达的识别能力。因而识别范围至少是个句子&#xff0c;最大范围就是文章&#xff0c;其研究方法有所区别。本文将按照目前高手的研究成绩&#xff0c;作为谈资介绍给诸位。 二、语义相似度简介 自然语言…...

WT2605-24SS高品质录音语音芯片:实时输出、不保存本地,引领音频技术新潮流

随着科技的快速发展&#xff0c;高品质音频技术成为了现代社会不可或缺的一部分。在这个追求高品质、高效率的时代&#xff0c;唯创知音推出的WT2605-24SS高品质录音芯片&#xff0c;以其独特的功能和卓越的性能&#xff0c;引领着音频技术的新潮流。 首先&#xff0c;WT2605-…...

Git 合并冲突解决步骤

Git 合并冲突解决步骤 1. 找到并打开冲突文件 定位到发生冲突的文件。可以通过 Git 的命令行输出找到这些文件。例如&#xff1a; pom.xmlsrc/main/java/com/zzm/config/SecurityConfig.javasrc/main/java/com/zzm/service/chat/UserConversationsServiceImpl.javasrc/main/…...

Windows核心编程 注册表

目录 注册表概述 打开关闭注册表 创建删除子健 查询写入删除键值 子健和键值的枚举 常用注册表操作 注册表概述 注册表是Windows操作系统、硬件设备以及客户应用程序得以正常运行和保存设置的核心"数据库"&#xff0c;也可以说是一个非常巨大的树状分层结构的…...

【算法专题】二分查找

二分查找 二分查找1. 二分查找2. 在排序数组中查找元素的第一和最后一个位置3. 搜索插入位置4. x 的平方根5. 山脉数组的峰顶索引6. 寻找峰值7. 寻找旋转排序数组中的最小值8. 点名 二分查找 1. 二分查找 题目链接 -> Leetcode -704.二分查找 Leetcode -704.二分查找 题…...

中国消费电子行业发展趋势及消费者需求洞察|徐礼昭

一、引言 近年来&#xff0c;随着科技的飞速发展&#xff0c;消费电子行业面临着前所未有的挑战与机遇。本文将从行业发展趋势、消费者需求洞察以及企业数字化转型的方向和动作三个方面&#xff0c;对消费电子行业进行深入剖析。 二、消费电子行业发展趋势 5G技术的普及和应…...

UE学习C++(1)创建actor

创建新C类 在 虚幻编辑器 中&#xff0c;点击 文件&#xff08;File&#xff09; 下拉菜单&#xff0c;然后选择 新建C类...&#xff08;New C Class...&#xff09; 命令&#xff1a; 此时将显示 选择父类&#xff08;Choose Parent Class&#xff09; 菜单。可以选择要扩展的…...

【CTA认证】Android8实现android6以下的应用运行时也要申请权限

需求 CTA入网认证&#xff0c;要求低版本比如Android6以下的应用&#xff0c;运行时&#xff0c;也需要有运行时权限(Runtime Permission)功能&#xff0c;不能默认就取到权限&#xff0c;必须人工在设置中打开才可。 环境 Android 8 实现 frameworks 修改思路是所有APP都…...

.Net框架,除了EF还有很多很多......

文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

Linux简单的操作

ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍

文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结&#xff1a; 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析&#xff1a; 实际业务去理解体会统一注…...

【HTML-16】深入理解HTML中的块元素与行内元素

HTML元素根据其显示特性可以分为两大类&#xff1a;块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...

uniapp中使用aixos 报错

问题&#xff1a; 在uniapp中使用aixos&#xff0c;运行后报如下错误&#xff1a; AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...

JS设计模式(4):观察者模式

JS设计模式(4):观察者模式 一、引入 在开发中&#xff0c;我们经常会遇到这样的场景&#xff1a;一个对象的状态变化需要自动通知其他对象&#xff0c;比如&#xff1a; 电商平台中&#xff0c;商品库存变化时需要通知所有订阅该商品的用户&#xff1b;新闻网站中&#xff0…...

PAN/FPN

import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...

Proxmox Mail Gateway安装指南:从零开始配置高效邮件过滤系统

&#x1f49d;&#x1f49d;&#x1f49d;欢迎莅临我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐&#xff1a;「storms…...

CVPR2025重磅突破:AnomalyAny框架实现单样本生成逼真异常数据,破解视觉检测瓶颈!

本文介绍了一种名为AnomalyAny的创新框架&#xff0c;该方法利用Stable Diffusion的强大生成能力&#xff0c;仅需单个正常样本和文本描述&#xff0c;即可生成逼真且多样化的异常样本&#xff0c;有效解决了视觉异常检测中异常样本稀缺的难题&#xff0c;为工业质检、医疗影像…...

HybridVLA——让单一LLM同时具备扩散和自回归动作预测能力:训练时既扩散也回归,但推理时则扩散

前言 如上一篇文章《dexcap升级版之DexWild》中的前言部分所说&#xff0c;在叠衣服的过程中&#xff0c;我会带着团队对比各种模型、方法、策略&#xff0c;毕竟针对各个场景始终寻找更优的解决方案&#xff0c;是我个人和我司「七月在线」的职责之一 且个人认为&#xff0c…...