LeetCode哈希表:最长连续序列
LeetCode哈希表:最长连续序列
题目描述
给定一个未排序的整数数组 nums ,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1:
输入:nums = [100,4,200,1,3,2]
输出:4
解释:最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
示例 2:
输入:nums = [0,3,7,2,5,8,4,6,0,1]
输出:9
解题思路
首先想到的方法就是先排序,然后再找到符合条件序列,但这样的话复杂度就不符合题目要求。最好的排序的是nlogn因此排序这条路走不通,考虑采用哈希,哈希的一个优点就是寻找元素容易,那就考虑怎么去找这个元素,两种方案,
- 第一种:找到一个序列最小值再以此向大的进行判断
- 第二种:找到一个序列最大的向小的方向判断
最后再返回最长长度
步骤如下:
- 创建HashSet:首先,创建一个
HashSet,用于存储数组中的元素。HashSet的目的是为了快速检查数组中是否包含某个元素,以及在O(1)时间内添加元素。 - 将数组元素加入HashSet:遍历输入数组
nums,将每个元素加入HashSet。 - 寻找连续序列:对于每个元素
num,检查是否存在num - 1,如果不存在,说明num可能是一个连续序列的起点。然后,从num开始,通过不断检查num + 1是否在HashSet中,来找到连续序列的长度。 - 更新最长连续序列的长度:在每次找到一个连续序列后,更新最长连续序列的长度。
- 返回结果:返回最终找到的最长连续序列的长度。
代码
public class hash2 {public int longestConsecutive(int[] nums) {HashSet<Integer> set=new HashSet<>();for (int num : nums) {set.add(num);}int ans=0;for (int num : set) {int right=num;if (!set.contains(right - 1)) {while (set.contains(right+1))right++;}ans=Math.max(ans,right-num+1);}return ans;}public static void main(String[] args) {hash2 ha=new hash2();System.out.println(ha.longestConsecutive(new int[]{100, 4, 200, 1, 3, 2}));}
}
优化以及其他思想的方法
- 方法1 哈希集合(最普遍也最简单的思路,必须掌握)
- 方法2 哈希表(思路1的进阶)
- 方法3 动态规划(极其巧妙,推荐掌握)
- 方法4 并查集(建议掌握)
传送:迪迦~~
相关文章:
LeetCode哈希表:最长连续序列
LeetCode哈希表:最长连续序列 题目描述 给定一个未排序的整数数组 nums ,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。 示例 1: 输入&…...
SpringBoot+redis实现接口防刷
写一个RedisService,实现获取Redis 的set、get、incr(相当于计数器) 写inferface注解类 做一个拦截器,因为要先于控制器判断 将拦截器注入Springboot 文章目录 目录 文章目录 前言 一、引入依赖 二、使用步骤 2.1 RedisServic…...
5G承载网和大客户承载的演进
文章目录 移动4/5G承载网联通和电信4/5G承载网M-OTN(Metro-optimized OTN),城域型光传送网PeOTN(packet enhanced optical transport network),分组增强型OTN板卡增强型PeOTN集中交叉型PeOTN VC-OTN&#x…...
智慧工地一体化解决方案(里程碑管理)源码
智慧工地为管理人员提供及时、高效、优质的远程管理服务,提升安全管理水平,确保施工安全提高施工质量。实现对人、机、料、法、环的全方位实时监控,变被动“监督”为主动“监控”。 一、建设背景 施工现场有数量多、分布广,总部统…...
熬夜会秃头——beta冲刺Day2
这个作业属于哪个课程2301-计算机学院-软件工程社区-CSDN社区云这个作业要求在哪里团队作业—beta冲刺事后诸葛亮-CSDN社区这个作业的目标记录beta冲刺Day2团队名称熬夜会秃头团队置顶集合随笔链接熬夜会秃头——Beta冲刺置顶随笔-CSDN社区 目录 一、团队成员会议总结 1、成员…...
【linux】信号——信号保存+信号处理
信号保存信号处理 1.信号保存1.1信号其他相关概念1.2信号在内核中的表示 2.信号处理2.1信号的捕捉流程2.2sigset_t2.3信号集操作函数2.4实操2.5捕捉信号的方法 3.可重入函数4.volatile5.SIGCHLD信号 自我名言:只有努力,才能追逐梦想,只有努力…...
雷军:我的程序人生路
今天有朋友发给我一篇我在20年前在BBS上写的帖子。那还是1996年,我们通过电话线拨号连接到西点BBS上飙帖子玩的年代。那是一个互联网混沌初开的年代,那是一个BBS和Email几乎主宰了全部互联网的年代,那是一个青春的理想和热血沸腾的年代。 我…...
Linux 磁盘分区处理
最近实施过程中遇到客户提供给我们的服务器操作系统和Docke容器环境都已经安装完成,但磁盘的分区没有进行整理好。磁盘总共270G,系统安装分配了60G,剩余未创建分配需要处理。由于分区情况每家不一样,但大致流程都是相同的…...
利用ogr2ogr从PostGIS中导出/导入Tab/Dxf/Geojson等格式数据
ogr2ogr Demo Command 先查看下当前gdal支持的全部格式,部分gdal版本可能不支持PostGIS。 如出现PostgreSQL表名支持。 #全部支持的格式 ogrinfo --formats | sort #AVCBin -vector- (rov): Arc/Info Binary Coverage #AVCE00 -vector- (rov): Arc/Info E00 (ASC…...
【深度优先】LeetCode1932:合并多棵二叉搜索树
作者推荐 动态规划LeetCode2552:优化了6版的1324模式 题目 给你 n 个 二叉搜索树的根节点 ,存储在数组 trees 中(下标从 0 开始),对应 n 棵不同的二叉搜索树。trees 中的每棵二叉搜索树 最多有 3 个节点 ࿰…...
monorepo多项目管理主流实现方式:1.learn + yarn/npm workspace 2.pnpm
npm域级包 随着npm包越来越多,而且包名也只能是唯一的,如果一个名字被别人占了,那你就不能再使用这个名字;假设我想要开发一个utils包,但是张三已经发布了一个utils包,那我的包名就不能叫utils了ÿ…...
【斗罗二】暗杀霍雨浩行动,马小桃霸气回击,江楠楠首秀武魂兔兔
Hello,小伙伴们,我是拾荒君。 《斗罗大陆Ⅱ绝世唐门》第25集更新了!和小伙伴们一样,一更新,拾荒君就急不可待地观看这一集。故事情节高潮迭起,尤其是霍雨浩与王冬面对六名杀手的惊险场景,真是让人心跳加速…...
[ 蓝桥杯Web真题 ]-年度明星项目
目录 引入 介绍 准备 目标 效果 规定 思路 知识补充 解答参考 引入 hello,大家好!我注意到了之前发的一篇蓝桥杯Web应用开发的文章是关注度最高的,可能大部分关注我的小伙伴对蓝桥杯Web应用开发比较感兴趣,或者想要参加…...
Maven终端打包时报Unknown lifecycle phase “.test.skip=true“
错误实例代码 mvn clean package -Dmaven.test.skiptrue 再windows的cmd窗口进行项目打包,需要将参数用英文符号包裹起来“ ” 【正确的实例】:mvn clean package ’-Dmaven.test.skiptrue‘ PS D:\BaiduNetdiskDownload\qian\Springboot-Vue\bi…...
Linux MIPI 调试中常见的问题
一、概述 做嵌入式工作的小伙伴知道,有时候程序编写没有调试过程中费时,之间笔记里有 MIPI 摄像头驱动开发的过程,有需要的小伙伴可以参考:Linux RN6752 驱动编写。而我也是第一次琢磨 MIPI 协议,其中有很多不明白的地…...
使用极限网关助力 ES 集群无缝升级、迁移上/下云
在工作中大家可能会遇到以下这些场景: 自建 ES 集群需要平滑迁移到 XX 云;从 XX 云将 ES 集群迁移到自建机房;ES 集群进行跨版本升级,同时保留回退能力; 这些场景往往都还有个共同的需求:迁移过程要保证业…...
RedisTemplate的配置和讲解以及和StringRedisTemplate的区别
本文主要讲redisTempalte的几种常用的序列化方式 string,我们大部分情况下都希望存入redis的数据可读性强一些,并且value也不总是一个规则的类型,所以这里也是不用json序列化的原因,可以更自由方便,下边提供配置方法 …...
在oracle中的scn技术
SCN可以说是Oracle中一个很基础的部分,但同时它也是一个很重要的。它是系统中维持数据的一致性和顺序恢复的重要标志,是数据库非常重要的一种数据结构。 转载:深入剖析 - Oracle SCN机制详细解读 - 知乎 (zhihu.com)https://zhuanlan.zhihu.…...
LINUX 嵌入式C编程--信号编程
基本概念 信号是事件发生时对进程的通知机制,也可以把它称为软件中断。信号与硬件中断的相似之处在于能够打断程序当前执行的正常流程,其实是在软件层次上对中断机制的一种模拟。信号提供了一种处理异步事件的方法。 信号目的 **信号的目的是用来通信…...
Linux:优化原则
web系统的优化原则: 从单机到集群 对Linux系统自身的优化原则:...
FFmpeg 低延迟同屏方案
引言 在实时互动需求激增的当下,无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作,还是游戏直播的画面实时传输,低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架,凭借其灵活的编解码、数据…...
SCAU期末笔记 - 数据分析与数据挖掘题库解析
这门怎么题库答案不全啊日 来简单学一下子来 一、选择题(可多选) 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘:专注于发现数据中…...
Nginx server_name 配置说明
Nginx 是一个高性能的反向代理和负载均衡服务器,其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机(Virtual Host)。 1. 简介 Nginx 使用 server_name 指令来确定…...
Mac软件卸载指南,简单易懂!
刚和Adobe分手,它却总在Library里给你写"回忆录"?卸载的Final Cut Pro像电子幽灵般阴魂不散?总是会有残留文件,别慌!这份Mac软件卸载指南,将用最硬核的方式教你"数字分手术"࿰…...
《基于Apache Flink的流处理》笔记
思维导图 1-3 章 4-7章 8-11 章 参考资料 源码: https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...
AI编程--插件对比分析:CodeRider、GitHub Copilot及其他
AI编程插件对比分析:CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展,AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者,分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...
CMake控制VS2022项目文件分组
我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...
学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”
2025年#高考 将在近日拉开帷幕,#AI 监考一度冲上热搜。当AI深度融入高考,#时间同步 不再是辅助功能,而是决定AI监考系统成败的“生命线”。 AI亮相2025高考,40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕,江西、…...
Selenium常用函数介绍
目录 一,元素定位 1.1 cssSeector 1.2 xpath 二,操作测试对象 三,窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四,弹窗 五,等待 六,导航 七,文件上传 …...
JS手写代码篇----使用Promise封装AJAX请求
15、使用Promise封装AJAX请求 promise就有reject和resolve了,就不必写成功和失败的回调函数了 const BASEURL ./手写ajax/test.jsonfunction promiseAjax() {return new Promise((resolve, reject) > {const xhr new XMLHttpRequest();xhr.open("get&quo…...
