Leetcode 最长连续序列

在这里插入图片描述

算法流程:

  1. 哈希集合去重

    • 通过将数组中的所有元素放入 unordered_set,自动去除重复元素。集合的查找操作是 O(1),这为后续的快速查找提供了保证。
  2. 遍历数组

    • 遍历数组中的每一个元素。对于每个元素,首先检查它是否是某个连续序列的第一个元素。
    • 具体地,如果当前元素的前一个元素 (num - 1) 不在集合中,说明当前元素有可能是某个序列的开始。这是关键步骤,因为如果 num - 1 在集合中,说明当前元素是某个序列的中间元素,不需要再处理。
  3. 序列长度统计

    • 当确定当前元素为某个序列的起点时,进入一个循环,检查当前元素的后一个元素 (num + 1num + 2、… ) 是否存在于集合中。
    • 利用 count() 来检查每个右邻元素是否存在,如果存在则将 currentStreak 加 1 继续统计,直到右邻元素不再存在。
  4. 更新最大长度

    • 每当一个序列结束时,使用 max() 函数更新全局的最大序列长度 longestStreak

代码结构与逻辑重点:

  • 哈希集合的使用 保证了我们能够在 O(1) 时间内查找某个元素是否存在。
  • 通过判断左邻元素是否存在 确保我们只对可能的序列起点进行处理,避免了对所有元素都重复计算。
  • count() 函数的 O(1) 查找时间 确保了我们能在常数时间内判断右邻元素是否存在,从而以线性时间完成整个数组的遍历和处理。

通过哈希集合的使用,算法避免了排序操作(O(n log n)),从而保证了线性时间复杂度 O(n)。

算法思路:

首先利用数组所有元素来初始化一个哈希集(unordered_set),由于集合性质,这一步会自动去除重复元素。

然后我们再去遍历数组每个元素,仅当当前元素是可能是某个最长连续序列的第一个元素时 (左邻元素不存在于哈希集中),我们进行序列长度统计

所以,如果当前元素的前一个相邻元素(num - 1)存在于哈希集中,那么说明当前元素必然不可能是某个最长连续序列的开始元素。这种情况下我们跳过不予处理。

再回到如果当前元素的确是某个可能的最长连续序列的第一个元素时,我们利用 STL 容器的成员函数 count() 来判断当前元素的右邻元素是否存在于哈希集中,并使用一个新的变量(currentStreak)来统计当前最长连续序列的长度,

unordered_set 中,count() 函数的主要作用是检查某个值是否存在于集合中。因为 unordered_set 只存储唯一的元素,因此 count() 要么返回 0,要么返回 1

  • 返回 0:表示该元素不在集合中。
  • 返回 1:表示该元素在集合中。

如果右邻元素存在于哈希集,那么currentStreak 加1,如果不存在于哈希集中则直接跳出循环。

每当跳出循环时,意味着最近一次处理的连续序列的长度已经统计结束,需要和上一次处理的连续序列的长度(currentStreak)进行 max 对比并更新currentStreak

class Solution {
public:int longestConsecutive(vector<int>& nums) {//初始化一个无序集合并且将nums数组中的元素全部加入到这个集合中unordered_set<int> numSet(nums.begin(), nums.end());//最长序列长度int longestStreak = 0;for(int num : nums) {if(numSet.count(num - 1) == 0) {//如果当前元素的前一个连续元素并不存在于集合中,说明当前元素有可能是一个最长连续序列的开头//并且这个最长连续序列目前至少长度为1int currentStreak = 1;//然后逐个+1并在集合中判断是否存在,直到不存在时终止int currentNum = num;while(numSet.count(currentNum + 1)) {currentStreak++;currentNum++;}longestStreak = max(longestStreak, currentStreak);}}return longestStreak;}
};

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

大数据新视界 --大数据大厂之Kafka消息队列实战:实现高吞吐量数据传输

&#x1f496;&#x1f496;&#x1f496;亲爱的朋友们&#xff0c;热烈欢迎你们来到 青云交的博客&#xff01;能与你们在此邂逅&#xff0c;我满心欢喜&#xff0c;深感无比荣幸。在这个瞬息万变的时代&#xff0c;我们每个人都在苦苦追寻一处能让心灵安然栖息的港湾。而 我的…

Ansys HFSS的边界条件与激励端口

本文将介绍HFSS边界条件、激励端口,然后重点介绍连接器信号完整性仿真应用最多的波端口(wave port)及其尺寸设置要点。 HFSS (电磁仿真)边界条件 HFSS中所谓的边界并非真正意义上的边界,边界条件是指定问题区域和对象边缘的场行为接口。在HFSS的背景下,边界的存在主要有两个…

[Linux入门]---使用exec函数实现简易shell

文章目录 1.简易实现2.人机交互&#xff0c;获取命令行3.命令行分割4.执行命令5.内建命令6.myshell代码 1.简易实现 2.人机交互&#xff0c;获取命令行 代码如下&#xff1a; int quit0; #define LEFT "[" #define RIGHT "]" #define LABLE "#&quo…

布偶猫应该喂什么猫罐头:交响乐金罐、希喂、尾巴生活测评

布偶猫&#xff0c;萌宠界的甜心代表&#xff0c;爱撒娇又黏人。想让它健康成长&#xff1f;喂养是关键。选粮不当&#xff0c;健康受损。今日精选三款热门主食罐&#xff0c;依据布偶猫营养需求&#xff0c;直接评测&#xff0c;助你快速了解何为理想之选。无需繁琐&#xff0…

Geneformer中文教程(2).huggingface transformers

Geneformer基于hugging face的transformers实现&#xff0c;具体模型是BertForSequenceClassification&#xff0c;本篇先熟悉该模型。 首先直观看Geneformer的模型架构&#xff0c;基于BERT构建一个文本分类模型&#xff0c;我们直接从预训练的Geneformer加载BERT&#xff0c…

为什么mac打不开rar文件 苹果电脑打不开rar压缩文件怎么办

你是否遇到过这样的情况&#xff0c;下载了一个rar文件&#xff0c;想要查看里面的内容&#xff0c;却发现Mac电脑无法打开。rar文件是一种常见的压缩文件格式&#xff0c;它可以将多个文件或文件夹压缩成一个文件&#xff0c;节省空间和传输时间。如此高效实用的压缩文档&…

自动驾驶:LQR、ILQR和DDP原理、公式推导以及代码演示(七、CILQR约束条件下的ILQR求解)

&#xff08;七&#xff09;CILQR约束条件下的ILQR求解 CILQR&#xff08;(Constrained Iterative Linear Quadratic Regulator)&#xff09; 是为了在 iLQR 基础上扩展处理控制输入和状态约束的问题。在这种情况下&#xff0c;系统不仅要优化控制输入以最小化代价函数&#x…

Python 课程9-資料庫操作

前言 在现代软件开发中&#xff0c;数据库是核心组件之一&#xff0c;它负责数据的存储、管理和检索。无论是简单的应用程序还是复杂的企业级系统&#xff0c;数据库操作都是必不可少的。本教程将深入讲解如何使用 Python 进行数据库操作&#xff0c;涵盖使用 sqlite3 进行本地…

《论网络安全体系设计》写作框架,软考高级系统架构设计师

论文真题 随着社会信息化的普及&#xff0c;计算机网络已经在各行各业得到了广泛的应用。目前&#xff0c;绝大多数业务处理几乎完全依赖计算机和网络执行&#xff0c;各种重要数据如政府文件、工资档案、财务账目和人事档案等均依赖计算机和网络进行存储与传输。另一方面&…

从用户数据到区块链:Facebook如何利用去中心化技术

在数字化时代&#xff0c;用户数据的管理和保护已成为科技公司面临的重大挑战。作为全球最大的社交网络平台之一&#xff0c;Facebook不仅在用户数据的处理上积累了丰富的经验&#xff0c;也在探索如何利用去中心化技术&#xff0c;如区块链&#xff0c;来改进其数据管理和用户…

Kafka原理剖析之「Topic创建」

一、前言 Kafka提供了高性能的读写&#xff0c;而这些读写操作均是操作在Topic上的&#xff0c;Topic的创建就尤为关键&#xff0c;其中涉及分区分配策略、状态流转等&#xff0c;而Topic的新建语句非常简单 bash kafka-topics.sh \ --bootstrap-server localhost:9092 \ // …

【刷题】Day4--密码检查

Hi&#xff01; 今日刷题&#xff0c;小白一枚&#xff0c;欢迎指导 ~ 【链接】 密码检查_牛客题霸_牛客网 【思路】 依次根据规则判断密码是否合格。while里嵌套个for循环&#xff0c;来进行密码的多组输入&#xff0c;for循环进行一次代表判断一个密码串&#xff1b;规则…

springboot请求传参常用模板

注释很详细&#xff0c;直接上代码 项目结构 源码 HelloController package com.amoorzheyu.controller;import com.amoorzheyu.pojo.User; import org.springframework.format.annotation.DateTimeFormat; import org.springframework.web.bind.annotation.*;import java.ti…

2024桥梁科技两江论坛——第二届桥梁工程安全与韧性学术会议

文章目录 一、会议详情二、重要信息三、大会介绍四、出席嘉宾五、征稿主题六、咨询 一、会议详情 二、重要信息 大会官网&#xff1a;https://ais.cn/u/vEbMBz提交检索&#xff1a;EI Compendex、IEEE Xplore、Scopus 三、大会介绍 2024年桥梁科技两江论坛——第二届桥梁工程…

一种简单的过某宝验证码的方式(仅做学习使用)

开篇 今天介绍一种简单的过某宝验证码的方式&#xff0c;用的是自动化&#xff0c;这样对不会js逆向的小白非常友好&#xff0c;只需要用到selenium框架就能轻松过某宝验证码&#xff0c;即模拟人的操作对滑块进行滑动。 但是首先还是需要训练验证码和标题 训练前&#xff1a…

基于微信小程序的图书馆预约占座系统

作者&#xff1a;计算机学姐 开发技术&#xff1a;SpringBoot、SSM、Vue、MySQL、JSP、ElementUI、Python、小程序等&#xff0c;“文末源码”。 专栏推荐&#xff1a;前后端分离项目源码、SpringBoot项目源码、SSM项目源码 系统展示 基于微信小程序JavaSpringBootVueMySQL的图…

GD - GD32350R_EVAL - PWM实验和验证3 - EmbeddedBuilder - 无源蜂鸣器 - 用PMOS来控制

文章目录 GD - GD32350R_EVAL - PWM实验和验证3 - EmbeddedBuilder - 无源蜂鸣器 - 用PMOS来控制概述笔记失败图成功图蜂鸣器管脚波形总结END GD - GD32350R_EVAL - PWM实验和验证3 - EmbeddedBuilder - 无源蜂鸣器 - 用PMOS来控制 概述 以前做了一个实验&#xff0c;用PMOS来…

智能智造和工业软件研发平台SCSAI功能介绍

用爱编程30年&#xff0c;倾心打造工业和智能智造软件研发平台SCIOT,用创新的方案、大幅的让利和极致的营销&#xff0c;致力于为10000家的中小企业实现数字化转型&#xff0c;打造数字化企业和智能工厂&#xff0c;点击上边蓝色字体&#xff0c;关注“AI智造AI编程”或文末扫码…

element-plus表单使用show-overflow-tooltip,避免占满屏幕,需要设置宽度

在表单中&#xff0c;<el-table-clumn>中添加show-overflow-tooltip&#xff0c;可以实现表格内容过多的问题。 属性官方解释&#xff1a;是否隐藏额外内容并在单元格悬停时使用 Tooltip 显示它们。 出现的问题&#xff1a; 使用了该属性之后&#xff0c;弹出的详细内…

Linux 手动安装Ollama

Linux 离线安装Ollama 前言 不知道为什么 在阿里云服务器上 执行curl -fsSL https://ollama.com/install.sh | sh一键安装 非常慢 所以只能手动装了 1.到 https://ollama.com/install.sh 下载安装执行文件 修改其中 下载和安装部分代码 if curl -I --silent --fail --location…