最长连续序列[中等]
优质博文:IT-BLOG-CN
一、题目
给定一个未排序的整数数组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
0 <= nums.length <= 105
-109 <= nums[i] <= 109
二、代码
【1】我们首先先当的是非O(n)的方法,对nums进行排序后判断最长连续序列。
class Solution {public int longestConsecutive(int[] nums) {// 我们首先想到的就是非O(N)的时间复杂度,先排序,在去重。if (nums == null || nums.length == 0) {return 0;}Arrays.sort(nums);Set<Integer> set = new LinkedHashSet<>();for (int i = 0; i < nums.length; i++) {set.add(nums[i]);}int maxLen = 1;int count = 1;int pre = Integer.MIN_VALUE;for (int num : set) {if (num - pre == 1) {count++;} else {count = 1;}pre = num;maxLen = Math.max(maxLen, count);}return maxLen;}
}
【2】上面的方法不是O(n)时间复杂度,所以我们需要将排序和去重这个动作的O(nlogn)的复杂度降下来,可以通过哈希表存储数组中的数,这样查一个数是否存在就可以优化至O(1)的时间复杂度,仅仅是这样我们的算法时间复杂度最坏情况下还是会达到O(n2)(即外层需要枚举O(n)个数,内层需要暴力匹配O(n)次),无法满足题目的要求。但仔细分析这个过程,我们会发现其中执行了很多不必要的枚举,如果已知有一个x,x+1,x+2,⋯ ,x+y的连续序列,而我们却重新从x+1,x+2或者是x+y处开始尝试匹配,那么得到的结果肯定不会优于枚举x为起点的答案,因此我们在外层循环的时候碰到这种情况跳过即可。
增加了判断跳过的逻辑之后,时间复杂度是多少呢?外层循环需要O(n)的时间复杂度,只有当一个数是连续序列的第一个数的情况下才会进入内层循环,然后在内层循环中匹配连续序列中的数,因此数组中的每个数只会进入内层循环一次。根据上述分析可知,总时间复杂度为O(n),符合题目要求。
class Solution {public int longestConsecutive(int[] nums) {// 我们首先想到的就是非O(N)的时间复杂度,先排序,在去重。if (nums == null || nums.length == 0) {return 0;}Set<Integer> num_set = new HashSet<>();for (int i = 0; i < nums.length; i++) {num_set.add(nums[i]);}int maxLen = 0;for (int num : num_set) {// 先判断是否存在上一个数字,减少时间复杂度if (!num_set.contains(num - 1)){int count = 1;int currentNum = num;while (num_set.contains(currentNum + 1)) {currentNum += 1;count += 1;}maxLen = Math.max(maxLen, count);}}return maxLen;}
}
时间复杂度: O(n),其中n为数组的长度。具体分析已在上面正文中给出。
空间复杂度: O(n)。哈希表存储数组中所有的数需要O(n)的空间。
相关文章:
最长连续序列[中等]
优质博文:IT-BLOG-CN 一、题目 给定一个未排序的整数数组nums,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。请你设计并实现时间复杂度为O(n)的算法解决此问题。 示例 1: 输入:nums […...
设计模式-状态模式-笔记
状态模式State 在组件构建过程中,某些对象的状态经常面临变化,如何对这些变化进行有效的管理?同时又维持高层模块的稳定?“状态变化”模式为这一问题提供了一种解决方案。 经典模式:State、Memento 动机(…...
Java中for、foreach、stream区别和性能比较
文章目录 性能比较区别使用方式和行为 性能比较 最终总结:如果数据在1万以内的话,for循环效率高于foreach和stream;如果数据量在10万的时候,stream效率最高,其次是foreach,最后是for。另外需要注意的是如果数据达到10…...
[CSS] 文本折行
文本折行一般分为两种情况: CJK(Chinese/Japanese/Korean) 字符和非 CJK 字符。一般非 CJK 字符折行发生在两个单词的空格中间,见下图: 图中文本 “hello world” 包裹容器的宽度为 2rem,但是 hello 并没有…...
033-从零搭建微服务-日志插件(一)
写在最前 如果这个项目让你有所收获,记得 Star 关注哦,这对我是非常不错的鼓励与支持。 源码地址(后端):mingyue: 🎉 基于 Spring Boot、Spring Cloud & Alibaba 的分布式微服务架构基础服务中心 源…...
短期经济波动:均衡国民收入决定理论(三)
短期经济波动:国民收入决定理论(三) 文章目录 短期经济波动:国民收入决定理论(三)[toc]1 总需求曲线及其变动1.1 总需求曲线含义1.2 总需求曲线推导1.2.1 代数推导1.2.2 几何推导 1.3 AD曲线及其变动1.3.1 扩张性财政政策1.3.2 扩张性货币政策 2 总供给曲…...
电力感知边缘计算网关产品设计方案-网关软件架构
边缘计算网关采用ARM定制硬件平台架构,包含上位机端(内网)和FPGA网关端(外网)两部分,通过芯片间的高速信号总线实现边缘计算网关工业数据采集、数据实时传输、数据存储、网关状态信息收集等功能。 边缘计算网关上位机端(内网)重点完成工业数据采集、业务软件运算、客户…...
最新AI创作系统ChatGPT系统运营源码/支持最新GPT-4-Turbo模型/支持DALL-E3文生图
一、AI创作系统 SparkAi创作系统是基于OpenAI很火的ChatGPT进行开发的Ai智能问答系统和Midjourney绘画系统,支持OpenAI-GPT全模型国内AI全模型。本期针对源码系统整体测试下来非常完美,可以说SparkAi是目前国内一款的ChatGPT对接OpenAI软件系统。那么如…...
Java使用Redis的几种客户端介绍
Redis是一种高性能的内存数据库,可以提供快速的数据读写操作。在Java中使用Redis,需要使用Redis客户端。目前,Java中常用的Redis客户端有以下几种: Jedis Jedis是Java中最流行的Redis客户端之一,它提供了丰富的API和…...
程序员的护城河
程序员的护城河 算法,一定是过硬的算法!!!举个栗子:算法不硬吃大亏写在最后 算法,一定是过硬的算法!!! 其实会什么技术不重要,掌握多少种编程语言也不重要&a…...
常见面试题-MySQL软删除以及索引结构
为什么 mysql 删了行记录,反而磁盘空间没有减少? 答: 在 mysql 中,当使用 delete 删除数据时,mysql 会将删除的数据标记为已删除,但是并不去磁盘上真正进行删除,而是在需要使用这片存储空间时…...
信号的机制——信号处理函数的注册
在 Linux 操作系统中,为了响应各种各样的事件,也是定义了非常多的信号。我们可以通过 kill -l 命令,查看所有的信号。 # kill -l1) SIGHUP 2) SIGINT 3) SIGQUIT 4) SIGILL 5) SIGTRAP6) SIGABRT 7) SIGBUS …...
JS-项目实战-鼠标悬浮变手势(鼠标放单价上生效)
1、鼠标悬浮和离开事件.js //当页面加载完成后执行后面的匿名函数 window.onload function () {//get:获取 Element:元素 By:通过...方式//getElementById()根据id值获取某元素let fruitTbl document.getElementById("fruit_tbl");//table.rows:获取这个表格…...
redis运维(十一) python操作redis
一 python操作redis ① 安装pyredis redis常见错误 说明:由于redis服务器是5.0.8的,为了避免出现问题,默认最高版本的即可 --> 适配 ② 操作流程 核心:获取redis数据库连接对象 ③ Python 字符串前面加u,r,b的含义 原因: 字符串在…...
黑马程序员微服务 第五天课程 分布式搜索引擎2
分布式搜索引擎02 在昨天的学习中,我们已经导入了大量数据到elasticsearch中,实现了elasticsearch的数据存储功能。但elasticsearch最擅长的还是搜索和数据分析。 所以今天,我们研究下elasticsearch的数据搜索功能。我们会分别使用DSL和Res…...
什么是UV贴图?
UV 是与几何图形的顶点信息相对应的二维纹理坐标。UV 至关重要,因为它们提供了表面网格与图像纹理如何应用于该表面之间的联系。它们基本上是控制纹理上哪些像素对应于 3D 网格上的哪个顶点的标记点。它们在雕刻中也很重要。 为什么UV映射很重要? 默认情…...
从哪里下载 Oracle database 11g 软件
登入My Oracle Support,选择Patches & Updates 标签页,点击下方的Latest Patchsets链接: 然后单击Oracle Database,就可以下载11g软件了: 安装单实例数据库需要1和2两个zip文件,安装GI需要第3个zip文…...
Ingress安全网关
目录 文章目录 目录本节实战TCP 流量拆分🚩 实战:TCP 流量拆分-2023.11.15(测试成功) Ingress安全网关Kubernetes Ingress🚩 实战:Kubernetes Ingress-2023.11.15(测试成功) Ingress GatewayIngress Gateway🚩 实战&am…...
Jmeter控制RPS
一、前言 RPS (Request Per Second)一般用来衡量服务端的吞吐量,相比于并发模式,更适合用来摸底服务端的性能。我们可以通过使用 JMeter 的常数吞吐量定时器来限制每个线程的RPS。对于RPS,我们可以把他理解为我们的TPS,我们就不…...
【Nginx】转发配置nginx.conf
文章目录 NginxNginx主要作用转发配置相关问题参考推荐阅读 Nginx Nginx (engine x) 是一个高性能的HTTP和反向代理web服务器,同时也提供了IMAP/POP3/SMTP服务。Nginx是由伊戈尔赛索耶夫为俄罗斯访问量第二的Rambler.ru站点(俄文:Рамбл…...
RestClient
什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端,它允许HTTP与Elasticsearch 集群通信,而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级ÿ…...
【2025年】解决Burpsuite抓不到https包的问题
环境:windows11 burpsuite:2025.5 在抓取https网站时,burpsuite抓取不到https数据包,只显示: 解决该问题只需如下三个步骤: 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...
ServerTrust 并非唯一
NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...
【JavaWeb】Docker项目部署
引言 之前学习了Linux操作系统的常见命令,在Linux上安装软件,以及如何在Linux上部署一个单体项目,大多数同学都会有相同的感受,那就是麻烦。 核心体现在三点: 命令太多了,记不住 软件安装包名字复杂&…...
如何理解 IP 数据报中的 TTL?
目录 前言理解 前言 面试灵魂一问:说说对 IP 数据报中 TTL 的理解?我们都知道,IP 数据报由首部和数据两部分组成,首部又分为两部分:固定部分和可变部分,共占 20 字节,而即将讨论的 TTL 就位于首…...
Java多线程实现之Thread类深度解析
Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...
Mysql中select查询语句的执行过程
目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析(Parser) 2.4、执行sql 1. 预处理(Preprocessor) 2. 查询优化器(Optimizer) 3. 执行器…...
Linux nano命令的基本使用
参考资料 GNU nanoを使いこなすnano基础 目录 一. 简介二. 文件打开2.1 普通方式打开文件2.2 只读方式打开文件 三. 文件查看3.1 打开文件时,显示行号3.2 翻页查看 四. 文件编辑4.1 Ctrl K 复制 和 Ctrl U 粘贴4.2 Alt/Esc U 撤回 五. 文件保存与退出5.1 Ctrl …...
LRU 缓存机制详解与实现(Java版) + 力扣解决
📌 LRU 缓存机制详解与实现(Java版) 一、📖 问题背景 在日常开发中,我们经常会使用 缓存(Cache) 来提升性能。但由于内存有限,缓存不可能无限增长,于是需要策略决定&am…...
MinIO Docker 部署:仅开放一个端口
MinIO Docker 部署:仅开放一个端口 在实际的服务器部署中,出于安全和管理的考虑,我们可能只能开放一个端口。MinIO 是一个高性能的对象存储服务,支持 Docker 部署,但默认情况下它需要两个端口:一个是 API 端口(用于存储和访问数据),另一个是控制台端口(用于管理界面…...
