最长连续序列[中等]
优质博文: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站点(俄文:Рамбл…...
多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度
一、引言:多云环境的技术复杂性本质 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时,基础设施的技术债呈现指数级积累。网络连接、身份认证、成本管理这三大核心挑战相互嵌套:跨云网络构建数据…...
盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来
一、破局:PCB行业的时代之问 在数字经济蓬勃发展的浪潮中,PCB(印制电路板)作为 “电子产品之母”,其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透,PCB行业面临着前所未有的挑战与机遇。产品迭代…...
【Linux】C语言执行shell指令
在C语言中执行Shell指令 在C语言中,有几种方法可以执行Shell指令: 1. 使用system()函数 这是最简单的方法,包含在stdlib.h头文件中: #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...
laravel8+vue3.0+element-plus搭建方法
创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...
MFC 抛体运动模拟:常见问题解决与界面美化
在 MFC 中开发抛体运动模拟程序时,我们常遇到 轨迹残留、无效刷新、视觉单调、物理逻辑瑕疵 等问题。本文将针对这些痛点,详细解析原因并提供解决方案,同时兼顾界面美化,让模拟效果更专业、更高效。 问题一:历史轨迹与小球残影残留 现象 小球运动后,历史位置的 “残影”…...
【JVM】Java虚拟机(二)——垃圾回收
目录 一、如何判断对象可以回收 (一)引用计数法 (二)可达性分析算法 二、垃圾回收算法 (一)标记清除 (二)标记整理 (三)复制 (四ÿ…...
uniapp 集成腾讯云 IM 富媒体消息(地理位置/文件)
UniApp 集成腾讯云 IM 富媒体消息全攻略(地理位置/文件) 一、功能实现原理 腾讯云 IM 通过 消息扩展机制 支持富媒体类型,核心实现方式: 标准消息类型:直接使用 SDK 内置类型(文件、图片等)自…...
CVE-2023-25194源码分析与漏洞复现(Kafka JNDI注入)
漏洞概述 漏洞名称:Apache Kafka Connect JNDI注入导致的远程代码执行漏洞 CVE编号:CVE-2023-25194 CVSS评分:8.8 影响版本:Apache Kafka 2.3.0 - 3.3.2 修复版本:≥ 3.4.0 漏洞类型:反序列化导致的远程代…...
Java + Spring Boot + Mybatis 插入数据后,获取自增 id 的方法
在 MyBatis 中使用 useGeneratedKeys"true" 获取新插入记录的自增 ID 值,可通过以下步骤实现: 1. 配置 Mapper XML 在插入语句的 <insert> 标签中设置: xml 复制 下载 运行 <insert id"insertUser" para…...
浅谈未来汽车电子电气架构发展趋势中的通信部分
目录 一、引入 1.1市场占比演化 1.2未来发展趋势 二、纯电动汽车与传统汽车的区别 2.1 纯电车和燃油车的架构(干货) 2.2 新能源汽车的分类 ⚡ 1. 纯电动汽车(BEV) 🔋 2. 插电式混合动力(PHEV&#…...
