首页 > 编程语言 >leetcode算法热题--最长连续序列

leetcode算法热题--最长连续序列

时间:2024-05-02 21:55:07浏览次数:24  
标签:hash nums -- res 复杂度 leetcode num 序列 热题

题目

给定一个未排序的整数数组 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 <= 10^5
-10^9 <= nums[i] <= 10^9

解答

思路与算法
我们一般都会想到先进行排序然后再去查找最长序列,但是普通的排序时间复杂度会达到O(nlogn),所以我们可以换一种思路来解答,我们可以先将数组内的值存储在哈希表中,然后我们遍历哈希表,我们先判断该值的前一个是否与其连续,如果连续我们就可以跳过这个值,如果不连续我们就判断其后面的连续的序列有几个,并用变量记录下来,最后就能得出最长序列。

代码
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> hash;
        for(auto num : nums)
        {
            hash.insert(num);
        }
        int res = 0;
        for(auto num : hash)
        {
            if (!hash.count(num - 1))
            {
                int currentnum = num;
                int tmp = 1;
                while(hash.count(currentnum+1))
                {
                    currentnum+=1;
                    tmp+=1;
                }
                res=max(tmp,res);
            }
        }
    return res;
    }
};
复杂度分析

时间复杂度:O(n)。使用一个for循环n次,虽然里面嵌套了while,但是while的时间复杂度为O(1)。
空间复杂度:O(n)。使用了一个哈希表来存储nums数组。

标签:hash,nums,--,res,复杂度,leetcode,num,序列,热题
From: https://www.cnblogs.com/oyoy/p/18170616

相关文章

  • Linux进程
    程序与进程程序:是可执行文件,其本质是是一个文件,程序是静态的,同一个程序可以运行多次,产生多个进程进程:它是程序的一次运行过程,当应用程序被加载到内存中运行之后它就称为了一个进程,进程是动态的,进程的生命周期是从程序运行到程序退出父子进程:当一个进程A通过frok()函数创建出进......
  • Makefile
    编译工具及构建工具介绍在之前的课程中,都是直接使用gcc对代码进行编译,这对简单的工程是可以的,但当我们遇到复杂的工程时,每次用gcc等编译工具去操作就会显得很低效。因此make工具就出现了,make的出现是为了解决手动编译和链接大型工程的问题,它可以避免重复的工作,提高效率,保证正确......
  • RISC-V SoC研发flow的总结
    RISC-VSoC研发flow的总结今年的流片接近尾声了,我个人的评价是相比去年,在进度管理和流程管理上做的更好了一些。对比今年一月份开会时开会的PPT,基本上当时的规划和目标基本上都达成了。这次聊聊整个研发过程中的一些感悟。首先是对于整个团队的研发方向做了一个比较大的修正,大概......
  • 操作系统
    定义:管理控制软/硬件资源,合理组织计算机工作流程以方便用户有效使用计算机程序集合。特点:并发,共享,虚拟,异步。结构:结构功能涌现。进程(程序+数据+PCB):有动态地址空间(代码,数据,PCB)执行完一个指令后,CPU都需要检查当前是否有外部中断信号,如果检查到外部中断信号,则需要保护被中断进程的CPU......
  • Let bygones be bygones
    Letbygonesbebygones.Oh,Ihave.欢乐dp场。总之我们通过神秘方法,一个像样的正解都没有写,获得了三位数的好成绩。六出祁山一个有脑子就会写的暴力dp,定义\(f_{i,j}\)表示处理到第\(i\)个,高度改为\(j\)。有\(f_{i,j}=f_{i-1,k}+|h_i-j|(|k-j|\leq......
  • FFmpeg常用命令案例记录
    音频转换mp3为ogg格式ffmpeg-iinput.mp3-c:alibvorbisoutput.ogg降低音量(例如50%)ffmpeg-iinput.mp3-af"volume=0.5"output.mp3视频转换mkv为mp4并进行无损压缩ffmpeg-iinput.mkv-c:vlibx264-crf18-presetslow-c:acopyoutput.mp4转换4K为10......
  • golang初学:交叉编译
    goversiongo1.22.1windows/amd64Windows11+amd64x86_64x86_64GNU/Linux--- 序章golang支持跨平台,支持的方式是在一个平台编译其它平台的可执行程序。本文介绍Windows11(开发主机)上编译Linux(目标主机)上的可执行程序。 #gobuild 开发主机和目标......
  • DRF之三大认证
    一、认证1、自定义认证在前面说的APIView中封装了三大认证,分别为认证、权限、频率。认证即登录认证,权限表示该用户是否有权限访问接口,频率表示用户指定时间内能访问接口的次数。整个请求最开始的也是认证。(1)需求登陆认证用户登陆成功--》签发token以后需要登陆才能访问的......
  • ​ Vue Router
    VueRouter是Vue.js官方的路由管理器(路径跳转)。它和Vue.js的核心深度集成,让构建单页面应用变得易如反掌。包含的功能有:嵌套的路由/视图表模块化的、基于组件的路由配置路由参数、查询、通配符基于Vue.js过渡系统的视图过渡效果细粒度的导航控制带有自动激活的C......
  • Buildroot+RISC-V+QEMU(@Ubuntu)运行
    1RISC-V相关Buildroot代码下载和编译下载Buildroot代码并切换特定分支:gitclonehttps://github.com/buildroot/buildroot.gitgitcheckout2024.02.1编译RISC-V的Buildroot:makeqemu_riscv64_virt_defconfigmake-j322在QEMU上运行RISC-V镜像进入output/images目录......