最长连续序列[中等]
优质博文: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站点(俄文:Рамбл…...
wordpress后台更新后 前端没变化的解决方法
使用siteground主机的wordpress网站,会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后,网站没有变化的情况。 不熟悉siteground主机的新手,遇到这个问题,就很抓狂,明明是哪都没操作错误&#x…...
RestClient
什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端,它允许HTTP与Elasticsearch 集群通信,而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级ÿ…...
连锁超市冷库节能解决方案:如何实现超市降本增效
在连锁超市冷库运营中,高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术,实现年省电费15%-60%,且不改动原有装备、安装快捷、…...
376. Wiggle Subsequence
376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...
[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?
论文网址:pdf 英文是纯手打的!论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误,若有发现欢迎评论指正!文章偏向于笔记,谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...
ServerTrust 并非唯一
NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...
【python异步多线程】异步多线程爬虫代码示例
claude生成的python多线程、异步代码示例,模拟20个网页的爬取,每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程:允许程序同时执行多个任务,提高IO密集型任务(如网络请求)的效率…...
【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)
骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术,它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton):由层级结构的骨头组成,类似于人体骨骼蒙皮 (Mesh Skinning):将模型网格顶点绑定到骨骼上,使骨骼移动…...
GC1808高性能24位立体声音频ADC芯片解析
1. 芯片概述 GC1808是一款24位立体声音频模数转换器(ADC),支持8kHz~96kHz采样率,集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器,适用于高保真音频采集场景。 2. 核心特性 高精度:24位分辨率,…...
python报错No module named ‘tensorflow.keras‘
是由于不同版本的tensorflow下的keras所在的路径不同,结合所安装的tensorflow的目录结构修改from语句即可。 原语句: from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后: from tensorflow.python.keras.lay…...
