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

leetcode刷题记录(四十八)——128. 最长连续序列

(一)问题描述

128. 最长连续序列 - 力扣(LeetCode)128. 最长连续序列 - 给定一个未排序的整数数组 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] <= 109icon-default.png?t=O83Ahttps://leetcode.cn/problems/longest-consecutive-sequence/description/?envType=study-plan-v2&envId=top-100-liked给定一个未排序的整数数组 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

 (二)解决思路

这道题目要求找连续序列,同时不要求序列位置连续,即查找数值大小上连续的元素有几个。那么使用哈希结构中的集合(Set)是最合适的:可以去除数组中重复的元素,又能快速找到符合条件的元素

思路很简单:

  • 找到序列的起始元素(即序列当中数值最小的元素)
  • 不断找到该序列中的下一个元素(比当前元素大一),每找到一个,序列长度就加一
  • 一个数组里可能包含多个序列,比较得到的多个长度取最大,就是当前数组中的最大连续序列长度。
class Solution {public int longestConsecutive(int[] nums) {//将给定数组转换为集合Set<Integer> s=new HashSet<>();for(int n : nums){s.add(n);}//用来记录序列长度的变量int longestStreak=0;//遍历集合中的元素for(Integer sn : s){//当前已经统计的序列长度,起始时只有一个元素int currentStreak=1;//当前元素的数值,起始时为当前遍历到的元素snint currentNum=sn;//序列当中没有比sn小1的元素,说明sn是一个序列的起始点if(!s.contains(sn-1)){   //只要有比sn大一的元素,就说明序列还没有结束,不断找序列中的下一个元素,同时序列长度加一while(s.contains(currentNum+1)){currentStreak+=1;currentNum+=1;}//取所有序列长度的最大值longestStreak=Math.max(longestStreak,currentStreak);}}return longestStreak;}
}

 (三)易错点

        这道题要求时间复杂度为O(n),那么就不能有排序,只要针对数组排序,时间复杂度就会大于O(n)。所以这道题解题的关键是想到找序列的起点,以及怎么找序列的节点。如果不找序列的起点,是没有办法按顺序累加元素的。

        另外也不是循环嵌套,时间复杂度就一定大于O(n)的哈。像这道题里面第二层循环的执行是有条件的,时间复杂度还是O(n)。

相关文章:

leetcode刷题记录(四十八)——128. 最长连续序列

&#xff08;一&#xff09;问题描述 128. 最长连续序列 - 力扣&#xff08;LeetCode&#xff09;128. 最长连续序列 - 给定一个未排序的整数数组 nums &#xff0c;找出数字连续的最长序列&#xff08;不要求序列元素在原数组中连续&#xff09;的长度。请你设计并实现时间复…...

HTML中如何保留字符串的空白符和换行符号的效果

有个字符串 储值门店{{thing3.DATA}}\n储值卡号{{character_string1.DATA}}\n储值金额{{amount4.DATA}}\n当前余额{{amount5.DATA}}\n储值时间{{time2.DATA}} &#xff0c; HTML中想要保留 \n的换行效果的有下面3种方法&#xff1a; 1、style 中 设置 white-space: pre-lin…...

Linux入门——环境基础开发(上)

Linux 软件包管理器 yum 什么是软件包 在Linux操作系统中&#xff0c;安装软件的方式通常较为复杂&#xff0c;其基本流程涉及下载程序源代码并通过编译得到可执行程序。然而&#xff0c;这种方法需要开发者具备一定的编程知识和环境配置能力&#xff0c;对于许多用户而言&am…...

c++类和对象---下

文章目录 一、类的静态成员 1.1.静态成员变量&#xff1a;所有对象共享的成员变量。 1.2.静态成员函数&#xff1a;可以访问静态成员变量&#xff0c;但不能访问非静态成员变量。 二、类的继承 2.1.继承&#xff1a;子类继承父类的成员变量和成员函数。 2.2.多态&#xff1a;基…...

组件中的Props

在项目开发中,在开发某些界面时,我们可以将一些代码封装成组件来简化代码。但是,如果某些情况下组件中的某些属性不是一成不变的(比如一个头像+姓名的组件,每次使用时都需要改变其图像src和姓名字符串),我们就可以使用Props。 我们要使用Props,我们需要先在组件中声明…...

并行服务、远程SSH无法下载conda,报错404

原下载代码无效&#xff0c;报错404 wget -c https://repo.anaconda.com/archive/Anaconda3-2023.03-1-Linux-x86_64.sh 使用下面代码下载 wget --user-agent"User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9.2.12) Gecko/20101026 Firefox/3.6.12…...

迅为RK3568开发板篇OpenHarmony配置HDF驱动控制LED-新增 topeet子系统-编写 bundle.json文件

bundle.json 文件内容如下所示&#xff1a; 下面是对各个字段的解释&#xff1a; 1. name: "ohos/demos" - 这是组件或项目的名称&#xff0c;这里表示它属于 OHOS&#xff08;OpenHarmony OS&#xff09;生态系统下的一个名为"demos"的组件。 2. descri…...

深度剖析RabbitMQ:从基础组件到管理页面详解

文章目录 一、简介二、Overview2.1 Overview->Totals2.2 Overview->Nodesbroker的属性2.3 Overview->Churn statistics2.4 Overview->Ports and contexts2.5 Overview->Export definitions2.6 Overview->Import definitions 三、Connections连接的属性 四、C…...

usb通过hdc连接鸿蒙next的常用指令

参考官方 注册报名https://www.hiascend.com/developer/activities/details/44de441ef599450596131c8cb52f7f8c/signup?channelCodeS1&recommended496144 hdc-调试命令-调测调优-系统 - 华为HarmonyOS开发者https://developer.huawei.com/consumer/cn/doc/harmonyos-guid…...

【落羽的落羽 C语言篇】文件操作

文章目录 一、文件的概念和分类1. 概念和分类2. 文件名3. 数据文件 三、文件操作1. 文件的打开和关闭1.1 流1.2 文件指针1.3 文件的打开和关闭 2. 文件的顺序读写3. 文件的随机读写4. 文件读取的判定5. 文件缓冲区 一、文件的概念和分类 1. 概念和分类 文件是用来保存数据的。…...

RNN之:LSTM 长短期记忆模型-结构-理论详解-及实战(Matlab向)

0.前言 递归&#xff01;循环神经网络Recurrent Neural Network 循环神经网络&#xff08;又称递归神经网络&#xff0c;Recurrent Neural Network&#xff0c;RNN&#xff09;。是一种用于处理序列数据的神经网络结构&#xff0c;具有记忆功能&#xff0c;能够捕捉序列中的时…...

战略与规划方法——深入解析波士顿矩阵(BCG Matrix):分析产品组合的关键工具

深入解析波士顿矩阵(BCG Matrix):分析产品组合的关键工具 在现代商业管理中,合理地分析和管理产品组合对于企业的成功至关重要。波士顿矩阵(BCG Matrix),又称为成长份额矩阵,是一种由波士顿咨询集团(Boston Consulting Group)在20世纪70年代提出的战略工具,用于帮助…...

【记录52】el-table-column 添加fixed属性 滚动条无法滑动

问题&#xff1a; el-table-column 添加fixed属性 滚动条无法滑动 使用element UI组件&#xff0c;用到el-table的el-table-column的fixed属性时&#xff0c;当滚动条长度小于固定列时&#xff0c;滚动条无法通过鼠标去点击滑动操作 原因 fixed是用来固定列的属性&#xff0c;其…...

晨辉面试抽签和评分管理系统之十:如何搭建自己的数据库服务器,使用本软件的网络版

晨辉面试抽签和评分管理系统&#xff08;下载地址:www.chenhuisoft.cn&#xff09;是公务员招录面试、教师资格考试面试、企业招录面试等各类面试通用的考生编排、考生入场抽签、候考室倒计时管理、面试考官抽签、面试评分记录和成绩核算的面试全流程信息化管理软件。提供了考生…...

主链和Layer2之间资产转移

主链和Layer2之间资产转移 主链和Layer2之间资产转移是实现Layer2技术的关键环节,以下是资产转移的流程、流行解决方案及原理: 资产从主链转移到Layer2 用户在主链上发起一笔交易,将资产发送到一个特定的智能合约地址,这个合约是主链与Layer2之间的桥梁。智能合约会锁定用…...

麒麟操作系统服务架构保姆级教程(十)rewrite跳转

如果你想拥有你从未拥有过的东西&#xff0c;那么你必须去做你从未做过的事情 我们访问一个网页的时候会遇到一些奇形怪状的url地址&#xff0c;想优化一下&#xff0c;看着顺眼一点&#xff0c;或者打开一个短视频软件想摸鱼刷一会视频&#xff0c;在打开界面的时候无意间按到…...

MySQL表的创建实验

创建并使用数据库mydb6_product 。 mysql> create database mydb6_product; Query OK, 1 row affected (0.01 sec)mysql> use mydb6_product; Database changed 新建employees表。 对于gender&#xff0c;有默认值意味着不为空&#xff0c;在建表时可以选择不写not nul…...

【高可用自动化体系】自动化体系

架构设计的愿景就是高可用、高性能、高扩展、高效率。为了实现架构设计四高愿景&#xff0c;需要实现自动化系统目标&#xff1a; 标准化。 流程自助化。 可视化&#xff1a;可观测系统各项指标、包括全链路跟踪。 自动化&#xff1a;ci/cd 自动化部署。 精细化&#xff1a…...

总结SpringBoot项目中读取resource目录下的文件多种方法

系列文章目录 提示&#xff1a;这里可以添加系列文章的所有文章的目录&#xff0c;目录需要自己手动添加 例如&#xff1a;第一章 Python 机器学习入门之pandas的使用 提示&#xff1a;写完文章后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目…...

Java-KMP字符串匹配算法

给两个字符串s和t&#xff0c;如何很快的知道s是否包含t&#xff08;即t是否是s的子串&#xff09;。暴力的方法&#xff0c;我们依次以s每个位置为头&#xff0c;去匹配t。 public int find(String s, String t) {char[] ss s.toCharArray();char[] tt t.toCharArray();int …...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】

微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来&#xff0c;Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互

引擎版本&#xff1a; 3.8.1 语言&#xff1a; JavaScript/TypeScript、C、Java 环境&#xff1a;Window 参考&#xff1a;Java原生反射机制 您好&#xff0c;我是鹤九日&#xff01; 回顾 在上篇文章中&#xff1a;CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

C# SqlSugar:依赖注入与仓储模式实践

C# SqlSugar&#xff1a;依赖注入与仓储模式实践 在 C# 的应用开发中&#xff0c;数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护&#xff0c;许多开发者会选择成熟的 ORM&#xff08;对象关系映射&#xff09;框架&#xff0c;SqlSugar 就是其中备受…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作

一、上下文切换 即使单核CPU也可以进行多线程执行代码&#xff0c;CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短&#xff0c;所以CPU会不断地切换线程执行&#xff0c;从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

C++使用 new 来创建动态数组

问题&#xff1a; 不能使用变量定义数组大小 原因&#xff1a; 这是因为数组在内存中是连续存储的&#xff0c;编译器需要在编译阶段就确定数组的大小&#xff0c;以便正确地分配内存空间。如果允许使用变量来定义数组的大小&#xff0c;那么编译器就无法在编译时确定数组的大…...

C++.OpenGL (20/64)混合(Blending)

混合(Blending) 透明效果核心原理 #mermaid-svg-SWG0UzVfJms7Sm3e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-icon{fill:#552222;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-text{fill…...

MySQL 部分重点知识篇

一、数据库对象 1. 主键 定义 &#xff1a;主键是用于唯一标识表中每一行记录的字段或字段组合。它具有唯一性和非空性特点。 作用 &#xff1a;确保数据的完整性&#xff0c;便于数据的查询和管理。 示例 &#xff1a;在学生信息表中&#xff0c;学号可以作为主键&#xff…...

作为测试我们应该关注redis哪些方面

1、功能测试 数据结构操作&#xff1a;验证字符串、列表、哈希、集合和有序的基本操作是否正确 持久化&#xff1a;测试aof和aof持久化机制&#xff0c;确保数据在开启后正确恢复。 事务&#xff1a;检查事务的原子性和回滚机制。 发布订阅&#xff1a;确保消息正确传递。 2、性…...

破解路内监管盲区:免布线低位视频桩重塑停车管理新标准

城市路内停车管理常因行道树遮挡、高位设备盲区等问题&#xff0c;导致车牌识别率低、逃费率高&#xff0c;传统模式在复杂路段束手无策。免布线低位视频桩凭借超低视角部署与智能算法&#xff0c;正成为破局关键。该设备安装于车位侧方0.5-0.7米高度&#xff0c;直接规避树枝遮…...

在 Spring Boot 中使用 JSP

jsp&#xff1f; 好多年没用了。重新整一下 还费了点时间&#xff0c;记录一下。 项目结构&#xff1a; pom: <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://ww…...