算法题(67):最长连续序列

审题:

需要我们在O(n)的时间复杂度下找到最长的连续序列长度

思路:
我们可以用两层for循环:

第一层是依次对每个数据遍历,让他们当序列的首元素。

第二层是访问除了该元素的其他元素

但是此时时间复杂度来到了n^2,不满足我们的需求

实际上我们的这个思路存在很多多余的枚举:

eg:5 4 3 2 1

如果我们按照前面的方法枚举,有:

1.5为首元素,size为1

2.4为首元素,size为2

3.3为首元素,size为3

4.2为首元素,size为4

5.1为首元素,size为5

而实际上有效的只有第五次枚举,因为我们是用了整个连续序列(12345)的首元素1.其他的size都是一定小于以真正首元素为头的size的

所以,我们利用哈希表辅助实现减少枚举次数的目的

方法一:哈希表

找到连续序列的首元素的方法:利用哈希表快速查找是否存在当前值-1的元素,若有则说明不是首元素,否则则是

解题:

第一步:利用unordered_set记录去除了重复数据的nums数组

在讲解去重的原理前,我们先了解一下unordered_set:

unordered_set:无序的记录带有唯一性数据的容器,且可以根据他们的值在O(1)的时间复杂度内找到他们

数据具有唯一性的原因:与unordered_map不同的是,unordered_set的值同时也是键,而由于键具有不可修改和唯一的特性,数据既不能修改也是唯一的(但是允许插入删除)

于是去重的原理就是unordered_set的数据具有唯一性

第二步:核心代码

遍历nums数组的每个元素,若发现该数据不是连续序列的首元素(因为用了unordered_set才能在O(1)时间复杂度下找到),则不进行任何操作直接跳过。

若是连续序列的首元素,则在哈希表中存储的数据中去寻找属于他的序列的元素,并存储为cursize,最后与maxszie进行比较,将较大的给到maxsize

128. 最长连续序列 - 力扣(LeetCode)

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

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

相关文章

2021年全国研究生数学建模竞赛华为杯E题信号干扰下的超宽带(UWB)精确定位问题求解全过程文档及程序

2021年全国研究生数学建模竞赛华为杯 E题 信号干扰下的超宽带(UWB)精确定位问题 原题再现: 一、背景   UWB(Ultra-Wideband)技术也被称之为“超宽带”,又称之为脉冲无线电技术。这是一种无需任何载波,通过发送纳秒…

Vue3折线图,柱状图,饼图,各种图表,适用于所有全平台

开发工具:HBuilderX编译器,uniapp,Vue3; 目标:全平台适用,Web端,小程序端,Android端,ios端,快应用等所有平台,鸿蒙app,前端&#xff…

联想电脑如何进入BIOS?

打开设置 下滑找到更新与安全 点击恢复和立即重新启动 选择疑难解答 选择UEFI固件设置 然后如果有重启点击重启 重启开机时一直点击FNF10进入BIOS界面

ICIR2025 | CubeDiff:重新利用基于扩散的图像模型来生成360°全景图

CubeDiff是一种使用基于扩散的图像模型生成 360 全景图的新型框架。通过利用立方体图表示和微调预训练的文本到图像模型,CubeDiff 简化了全景图生成过程,提供了高质量、一致的全景图。 CubeDiff 利用立方体图来表示 360 全景图,并在一次传递中…

YOLO11网络结构以及改进1

YOLO11 1.YOLO11网络结构图在哪里?2.对应的网络结构图3.每一个模块详解3.1 Conv模块3.2关于卷积模块3.3 关于给各个模块指定参数的细节 4.加入CBAM 1.YOLO11网络结构图在哪里? 2.对应的网络结构图 3.每一个模块详解 3.1 Conv模块 位置:ultr…

兔兔答题应用于微信考试、付费考试、社会调查问卷、明星知识问答、员工培训考核、模拟自测、企业面试、试题库等多种场景。

“兔兔答题系统”是一个面向教育、培训和在线测评场景的智能化答题平台(兔兔答题官网地址)。其设计目标是帮助用户高效完成题目练习、考试组织及学习效果分析,通常具备以下核心功能和特色: 一、核心功能 题库管理 支持多题型录入&…

网络安全防范

实践内容 学习总结 PDR,$$P^2$$DR安全模型。 防火墙(Firewall): 网络访问控制机制,布置在网际间通信的唯一通道上。 不足:无法防护内部威胁,无法阻止非网络传播形式的病毒,安全策略…

Java 设计模式之组合模式

文章目录 Java 设计模式之组合模式概述UML代码实现 Java 设计模式之组合模式 概述 组合模式(Composite):将对象组合成树形结构以表示’部分-整体’的层次结构。组合模式使得用户对单个对象和组合对象的使用具有一致性。优点:客户端可以统一处理单个对象…

基于VS2022在Windows上首次尝试开发C++ gRPC服务端和客户端的详细步骤

文章目录 **1. 创建解决方案与项目****2. 编写proto文件****3. 生成gRPC代码****4. 配置项目属性****服务端项目(gRPCServer)****客户端项目(gRPCClient)** **5. 实现服务端代码****6. 实现客户端代码****7. 编译与运行****注意事…

云创智城充电系统:基于 SpringCloud 的高可用、可扩展架构详解-多租户、多协议兼容、分账与互联互通功能实现

在新能源汽车越来越普及的今天,充电基础设施的管理和运营变得越来越重要。云创智城充电系统,就像一个超级智能管家,为新能源充电带来了全新的解决方案,让充电这件事变得更方便、更高效、更安全。 一、厉害的技术架构,让…

【第2章:神经网络基础与实现——2.4 实战案例:使用TensorFlow或PyTorch实现简单的MLP模型】

一、神经网络基础 咱先聊聊神经网络的基础概念。神经网络,简单来说,就是模仿人类大脑神经元结构构建的计算模型。它由大量的节点(也就是神经元)和连接这些节点的边组成。这些节点就像大脑里的一个个小处理器,而边则负责传递信息。 神经元 神经元是神经网络的基本单元。…

【Uniapp】关于实现下拉刷新的三种方式

在小程序、h5等地方中,常常会用到下拉刷新这个功能,今天来讲解实现这个功能的三种方式:全局下拉刷新,组件局部下拉刷新,嵌套组件下拉刷新。 全局下拉刷新 这个方式简单,性能佳,最推荐&#xf…

生成式聊天机器人 -- 基于Transformer实现的SeqToSeq模型 -- 上

生成式聊天机器人 -- 基于Transformer实现的SeqToSeq模型 -- 上 引言数据预处理下载并处理数据数据加载 Transformer模型嵌入层&位置编码层多头注意力机制EncoderLayerDecoderLayerPoint-wise Feed Forward NetworkTransformer 引言 在此之前,我们已经了解了如…

TCP文件传输

文件传输 工作原理 本质:客户端通过标准IO或者文件IO,读取文件中的信息 然后将读取到的信息,通过套接字发送给服务器 服务器接收到这些数据之后,立刻通过标准IO或者文件IO写到文件里面去 这个过程里面,服务器需要知道2件事情 1&…

欧拉函数杂记

定义 φ ( n ) \varphi (n) φ(n)表示 [ 1 , n ] [1,n] [1,n]中与 n n n互质的数的个数。 性质 φ ( p ) p − 1 , p ∈ P \varphi (p)p-1,\ p\in \mathbb {P} φ(p)p−1, p∈P φ ( n ) n ∏ i 1 m p i − 1 p i \varphi (n)n\prod_{i1}^{m} \frac{p_i-1}{p_i} φ(n)ni1∏…

在 CentOS 上更改 SSH 默认端口以提升服务器安全性

🚀 作者主页: 有来技术 🔥 开源项目: youlai-mall ︱vue3-element-admin︱youlai-boot︱vue-uniapp-template 🌺 仓库主页: GitCode︱ Gitee ︱ Github 💖 欢迎点赞 👍 收藏 ⭐评论 …

Spring Boot(8)深入理解 @Autowired 注解:使用场景与实战示例

搞个引言 在 Spring 框架的开发中,依赖注入(Dependency Injection,简称 DI)是它的一个核心特性,它能够让代码更加模块化、可测试,并且易于维护。而 Autowired 注解作为 Spring 实现依赖注入的关键工具&…

搜狗拼音输入法自定义短语设置

点击搜狗拼音输入法 选择设置 选择高级->自定义短语->自定义短语设置 选择添加新的短语 填入想设置的短语,点击确定 效果展示

反射概率以及一些基本API的使用

请问,获取对象有几种方式? 1、通过构造函数来new一个对象; 2、通过clone来克隆一个对象; 3、通过序列化反序列化来构建一个对象; 4、通过反射来创建对象;a、通过Class类来创建;b、通过Const…

从零搭建:Canal实时数据管道打通MySQL与Elasticsearch

Canal实时同步Mysql Binlog至 Elasticsearch 文章目录 Canal实时同步Mysql **Binlog**至**Elasticsearch** 一. 环境准备1.环境检查检查Mysql是否开启BinLog开启Mysql BinlogJava环境检查 2.新建测试库和表3.新建Es索引 二.**部署 Canal Server****2.1 解压安装包****2.2 配置 …