【力扣 Hot100 | 第六天】4.21(最长连续序列)

在这里插入图片描述

文章目录

  • 10.最长连续序列
    • 10.1题目
    • 10.2解法:哈希法
      • 10.2.1哈希思路
      • 10.2.2代码实现

10.最长连续序列

10.1题目

给定一个未排序的整数数组 nums ,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

  • 示例一:
输入:nums = [100,4,200,1,3,2]
输出:4
解释:最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
  • 示例二:
输入:nums = [0,3,7,2,5,8,4,6,0,1]
输出:9

10.2解法:哈希法

10.2.1哈希思路

  • 题目要求时间复杂度为O(n)
  • 核心:一次遍历,每个数都判断一次这个数是不是连续序列的开头那个数
    • 用哈希表查找这个数前面一个数是否存在,即num-1在序列中是否存在。存在那这个数肯定不是开头,直接跳过
    • 因此只需要对每个开头的数进行循环,直到这个序列不再连续,因此复杂度是O(n)。
  • 举例:[100,4,200,1,3,4,2] 去重后的哈希序列为:
    [100,4,200,1,3,2]
    按照上面逻辑进行判断:
    • 元素100是开头,因为没有99,且以100开头的序列长度为1
    • 元素4不是开头,因为有3存在,过,
    • 元素200是开头,因为没有199,且以200开头的序列长度为1
    • 元素1是开头,因为没有0,且以1开头的序列长度为4,因为依次累加,2,3,4都存在。
    • 元素3不是开头,因为2存在,过,
    • 元素2不是开头,因为1存在,过。

10.2.2代码实现

	public int longestConsecutive(int[] nums) {

        if(nums.length==0){
            return 0;
        }
        
        int res=Integer.MIN_VALUE;
        Set<Integer> set=new HashSet<>();
        for(int num:nums){
            set.add(num);
        }
        //1、遍历整个nums数组
        for(int num:nums){
            //2、判断 num 是否为有序序列的第一个元素
            if(set.contains(num-1)==false){

                //3、num为第一个元素

                int max=1;
                while(set.contains(num+1)){
                    num++;
                    max++;
                }
    
                //4、更新最长连续序列长度
                res=Math.max(res,max);
            }
        }
        return res;
         
    }

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/568424.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

php 编译安装oracel扩展

第一步安装Oracle客户端 1&#xff0c;需要下载基础包和sdk oracle客户端下载链接&#xff1a;Oracle Instant Client Downloads for Linux x86-64 (64-bit) https://www.oracle.com/database/technologies/instant-client/linux-x86-64-downloads.html 选择最新版本 versi…

国产PLC有哪些,哪个牌子比较好用?

你知道国产PLC有哪些吗,哪个牌子更好用吗&#xff1f; 今天拿出国产先锋的汇川与台达对比&#xff0c;注&#xff1a;视频后方有各品牌学习资料免费送&#xff0c;需要的移步自取。话说回来&#xff0c;只要基于Codesys开发的都比较好用&#xff0c;只是使用底层芯片不同&…

2013-2021年各省经济韧性相关测度指标面板数据

2013-2021年各省经济韧性相关测度指标面板数据 1、时间&#xff1a;2013-2021年 2、指标&#xff1a;城镇化率 %、财政科学技术支出&#xff08;亿元&#xff09;、万人高等教育在校人数&#xff08;万人&#xff09;、财政教育支出&#xff08;亿元&#xff09;、第三产业占…

AD 21、22 软件安装教程

AD2022安装包链接 链接&#xff1a;https://pan.baidu.com/s/1oMNbXibQ1Zjl0RTLdPDVGw 提取码&#xff1a;xfs4 软件下载 1.以管理员身份运行 2. 3. 4. 5.路径最好改为C盘以外的&#xff0c;如D盘&#xff0c;要新建一个空文件夹 6. 7.下载好以后 8.在Crack文件夹下找…

程序员周末提升计划:朝网络安全工程师转型之路

作为一名软件开发人员&#xff0c;我一直对网络安全充满兴趣&#xff0c;并希望在未来转型成为一名网络安全工程师。面对网络安全领域的挑战和机遇&#xff0c;我制定了一个周末提升计划&#xff0c;希望能系统地增强我的技能并为这一跨界做好准备。下面&#xff0c;我将分享我…

有没有学网络空间安全的学长,想知道学长们毕业以后都去干嘛了?

我作为一个零基础小白到白帽黑客&#xff0c;也认识到了很多零基础小白的&#xff0c;有一些网络空间安全的学员&#xff0c;但是大多数还是非计算机相关专业的学员。他们通过系统学习网络安全&#xff0c;掌握黑客技术之后&#xff0c;都找到了自己满意的工作。 同学A&#x…

软文发稿对于企业的重要性

随着社会的发展和科技的进步&#xff0c;软文发稿已成为企业和个人推广和传播信息的一种非常重要的方式。它以隐性的广告形式&#xff0c;通过内容发布&#xff0c;为品牌广告和产品推广铺设了一条隐形高速公路。下面我们就详细解析一下软文发稿的优点和好处。 软文发稿帮助增…

AutoDL运行SCRFD

pycharm-autodl 1.租服务器 3080ti 镜像&#xff1a;PyTorch 1.10.0 Python 3.8(ubuntu20.04) Cuda 11.3 2.jupyterLab激活conda vim ~/.bashrc在最底部添加 source /root/miniconda3/etc/profile.d/conda.sh重启 bash激活conda conda activate base3.pycharm远程连接aut…

【嵌入式AI部署神经网络】STM32CubeIDE上部署神经网络之指纹识别(Pytorch)——篇一|环境搭建与模型初步部署篇

前言&#xff1a;本篇主要讲解搭建所需环境&#xff0c;以及基于pytorch框架在stm32cubeide上部署神经网络&#xff0c;部署神经网络到STM32单片机&#xff0c;本篇实现初步部署模型&#xff0c;没有加入训练集与验证集&#xff0c;将在第二篇加入。篇二详细讲解STM32CubeIDE上…

基于研发过程改进的质量度量模型

随着企业规模和产品项目的不断扩张&#xff0c;全面、精准、高效地保障产品质量成为组织的核心挑战。为了应对这一挑战&#xff0c;企业应寻求采用数字化和智能化的研发过程管理方案&#xff0c;以实现对研发活动的精细化量化控制&#xff0c;并利用数据分析工具深入洞察产品质…

Interpreter 解释器

意图 给定一个语言&#xff0c;定义它的文法的一种表示&#xff0c;并定义一个解释器&#xff0c;这个解释器使用该表示来解释语言中的句子。 结构 AbstractExpression声明一个程序的解释操作&#xff0c;这个接口为抽象语法树中所有结点所共享。TerminalExpression实现与文法…

【IR 论文】Query2doc — 使用 LLM 做 Query Expansion 来提高信息检索能力

论文&#xff1a;Query2doc: Query Expansion with Large Language Models ⭐⭐⭐⭐⭐ Microsoft Research, EMNLP 2023 文章目录 背景介绍Query2doc 论文速读实现细节实验结果和分析总结分析 背景介绍 信息检索&#xff08;Information Retrieval&#xff0c;IR&#xff09;指…

谷歌收录工具有什么好用的?

如果是想促进谷歌的收录&#xff0c;其实能用的手段无非就两个&#xff0c;谷歌GSC以及爬虫池 谷歌gsc就不用说了&#xff0c;作为谷歌官方提供的工具&#xff0c;他能提供最准确的数据&#xff0c;并且可以提交每天更新的链接&#xff0c;进而促进收录&#xff0c;只要你的页面…

【unity】三维数学应用(计算线和面的交点)

【unity】三维数学应用&#xff08;计算线和面的交点&#xff09; 实现方法有多种&#xff0c;下面介绍一种简单的方法。利用一个点指向面上任意点的向量&#xff0c;到该面法线的投影长度相同的基本原理&#xff0c;结合相似三角形既可以求出交点。 原理 如下图 GD组成的线段…

Docker搭建Maven仓库Nexus

文章目录 一、简介二、Docker部署三、仓库配置四、用户使用Maven五、管理Docker镜像 一、简介 Nexus Repository Manager&#xff08;简称Nexus&#xff09;是一个强大的仓库管理器。 Nexus3支持maven、docker、npm、yum、apt等多种仓库的管理。 建立了 Maven 私服后&#xf…

大小端解释以及如何使用程序判断IDE的存储模式

今天让我们来了解一下大小端的概念吧 什么是大小端&#xff1f; 大端&#xff08;存储&#xff09;模式&#xff1a;指的是数据的低位保存在内存的高地址处&#xff0c;而数据的高位则保存在内存的低地址处。 小端&#xff08;存储&#xff09;模式&#xff1a;指的是数据的低位…

jvm中的垃圾回收器

Jvm中的垃圾回收器 在jvm中&#xff0c;实现了多种垃圾收集器&#xff0c; 包括&#xff1a; 1.串行垃圾收集器 2.并行垃圾收集器 3.CMS&#xff08;并发&#xff09;垃圾收集器 4.G1垃圾收集器 1.串行垃圾回收器 效率低&#xff0c;使用较少 2.并行垃圾回收器 3.并发垃圾回…

InternLM2-lesson3作业+笔记

茴香豆 https://www.bilibili.com/video/BV1QA4m1F7t4/?vd_source902e3124d4683c41b103f1d1322401fa 一、笔记 RAG RAG(Retrieval Augmented Generation)是一种结合了检索(Retrieval)和生成(Generation)的技术&#xff0c;旨在通过利用外部知识库来增强大预言模型的性能。…

ctfshow web入门 web180--web185

web180 import requests import recom re.compile("admin") def repisTrue(char):url f"http://自己环境的网址/api/?id1%27and%27{char}%27%27{char}&page1&limit10"res requests.get(url)w com.search(res.text)if w is not None:return T…

windows系统下python开发工具安装

一. 简介 前一篇文章学习了安装 python解释器&#xff0c;文章如下&#xff1a; windows系统下python解释器安装-CSDN博客 本文来学习如何下载安装 python开发工具 PyCharm。 二. python开发工具 PyCharm下载安装 1. PyCharm官网 PyCharm开发工具 PyCharm为 python代码…