【C++】每日一题 128 最长连续序列

news/2024/4/21 13:02:27/文章来源:https://blog.csdn.net/ZSZ_shsf/article/details/136573399

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

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

#include <iostream>
#include <vector>
#include <unordered_set>int longestConsecutiveSequence(const std::vector<int>& nums) {std::unordered_set<int> numSet(nums.begin(), nums.end());int maxLength = 0;for (int num : numSet) {// 只考虑当前数字作为序列起点的情况if (numSet.find(num - 1) == numSet.end()) {int currentNum = num;int currentLength = 1;while (numSet.find(currentNum + 1) != numSet.end()) {currentNum++;currentLength++;}maxLength = std::max(maxLength, currentLength);}}return maxLength;
}int main() {std::vector<int> nums = {100, 4, 200, 1, 3, 2};int result = longestConsecutiveSequence(nums);std::cout << "The length of the longest consecutive sequence is: " << result << std::endl;return 0;
}

这段代码首先将输入的整数数组构建为一个 unordered_set,以便快速查找数字是否存在。然后遍历数组中的每个数字,对于每个数字,判断是否存在比它小的数字(即作为某个序列的起点),如果不存在,则从该数字开始向后搜索连续的数字,计算当前连续序列的长度。最后更新最长连续序列的长度并返回。

整个算法的时间复杂度为 O(n),其中 n 为输入数组的长度,因为使用了哈希集合来存储数字,判断数字是否存在的时间复杂度为 O(1)。

不考虑时间复杂度,纯从解题角度还有一种解决方案:

int longestConsecutive(vector<int>& nums) {int len = nums.size();if (len == 0) {return 0;}int maxlen = 1;int maxt = 1;vector<int> numst = nums;unordered_map<int, int> m;sort(numst.begin(), numst.end());for (int i = 0; i < len; i++) {if (m.find(nums[i]) == m.end()) {m.insert(make_pair(nums[i], 1));}else {m[nums[i]] = m[nums[i]] + 1;}}for (int i = 0; i < len-1; i++) {if ((m.find(numst[i] + 1) != m.end())) {if (m[numst[i] + 1]) {maxt++;m[numst[i] + 1] = 0;}}else {maxt = 1;}maxlen = max(maxlen, maxt);}return maxlen;}
};

时间复杂度为 O(n log n),空间复杂度为 O(n)。

时间复杂度分析:

对输入数组 nums 进行排序的时间复杂度为 O(n log n)。
第一个 for 循环遍历整个数组并将元素及其出现次数存储在 unordered_map 中,时间复杂度为 O(n)。
第二个 for 循环遍历排序后的数组,对于每个元素,查找其是否存在相邻的元素,并更新最长连续序列的长度,时间复杂度为 O(n)。
综合以上步骤,总体时间复杂度为 O(n log n) + O(n) + O(n) = O(n log n)。

空间复杂度分析:

额外使用了一个大小为 n 的 vector numst 来存储 nums 的副本,空间复杂度为 O(n)。
使用了一个 unordered_map<int, int> m 来存储元素及其出现次数,空间复杂度也为 O(n)。
综合以上两部分,总体空间复杂度为 O(n)。

这个方案使用了排序和哈希表的方法来计算最长连续序列的长度。和上一个方案相比的优势和劣势:

优势:

排序后查找相邻元素更方便: 通过对数组进行排序,可以更容易地找到相邻的元素,从而判断是否存在连续序列。

使用哈希表存储元素及其出现次数: 哈希表在查找、插入操作上具有 O(1) 的时间复杂度,能够有效地存储元素及其出现次数,方便后续的查找和更新操作。

劣势:

时间复杂度较高: 使用排序的方法将时间复杂度提升到了 O(n log n),而哈希表的插入和查找操作虽然是 O(1),但仍需遍历整个数组,总体时间复杂度仍为 O(n log n)。

空间复杂度较高: 使用了额外的哈希表来存储元素及其出现次数,增加了空间复杂度。

逻辑复杂度高: 需要维护排序后的数组以及哈希表,增加了代码的复杂度和维护成本。

相比之下,前一种方案,代码逻辑清晰,且时间复杂度为 O(n),空间复杂度也较低,不需要额外的排序和哈希表操作。

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

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

相关文章

二维码门楼牌管理系统应用场景:推动旅游与文化产业的智慧化升级

文章目录 前言一、二维码门楼牌管理系统在旅游领域的应用二、二维码门楼牌管理系统在文化产业的应用三、结语 前言 随着信息技术的不断发展&#xff0c;二维码门楼牌管理系统作为一种创新的信息化手段&#xff0c;正在逐渐渗透到旅游和文化领域。它通过为文化景点、旅游景点和…

2024 批量下载公众号文章内容/阅读数/在看数/点赞数/留言数/粉丝数导出pdf文章备份(带留言):公众号爱在冰川近3000篇历史文章在线查看,找文章方便了

关于公众号文章批量下载&#xff0c;我之前写过很多文章&#xff1a; 视频更新版&#xff1a;批量下载公众号文章内容/话题/图片/封面/音频/视频&#xff0c;导出html&#xff0c;pdf&#xff0c;excel包含阅读数/点赞数/留言数 2021陶博士2006/caoz的梦呓/刘备我祖/六神读金…

qnx启动中控屏黑屏

bmetrics_service boot metrics service, 用于记录统计启动性能信息,读取/dev/bmetrics可以获取到这些信息 # use memorydump memorydump Sets the debug cookies, copies MMU info into reset_info asinfo, sets the secure monitor(TZ) dump buffer, starts tracelogger Usa…

菜鸟笔记-14散点图标记形状

大家在学习Python科研绘图中&#xff0c;总会涉及散点图标记形状&#xff0c;为了方便大家学习应用&#xff0c;博主通过学习搜集&#xff0c;将这部分技巧总结如下。 14.1默认散点图 14.1.1图像呈现 14.1.2绘图代码 import numpy as np # 导入numpy库&#xff0c;用于处理…

CDN(内容分发网络):加速网站加载与优化用户体验

&#x1f90d; 前端开发工程师、技术日更博主、已过CET6 &#x1f368; 阿珊和她的猫_CSDN博客专家、23年度博客之星前端领域TOP1 &#x1f560; 牛客高级专题作者、打造专栏《前端面试必备》 、《2024面试高频手撕题》 &#x1f35a; 蓝桥云课签约作者、上架课程《Vue.js 和 E…

Vue | 基于 vue-admin-template 项目的跨域问题解决方法

目录 一、现存问题 二、解决方法 2.1 修改的第一个地方 2.2 修改的第二个地方 2.3 修改的第三个地方 自存 一、现存问题 报错截图如下&#xff1a; 二、解决方法 2.1 修改的第一个地方 在 .env.development 文件中&#xff1a; # base api # VUE_APP_BASE_API /d…

基于Jupyter快速入门Python,Numpy,Scipy,Matplotlib

文章目录 Jupyter 和 Colab 笔记本PythonPython 版本基础数据类型数字Numbers布尔值Booleans字符串Strings 容器列表List字典Dictionaries集合Sets元组Tuples 函数类 Numpy数组Array数组索引Array indexing数据类型DatatypesArray math广播Broadcasting Scipy图像操作MATLAB文件…

智慧城市中的数字孪生:构建城市管理的未来框架

目录 一、引言 二、数字孪生技术概述 三、数字孪生技术在智慧城市中的应用 1、实时监测与预警 2、模拟与优化 3、智能化决策 4、协同与共享 四、数字孪生技术构建城市管理的未来框架的价值 1、提高管理效率 2、优化资源配置 3、提升公共服务水平 4、增强应对突发事…

耐腐蚀特氟龙塑料材质PFA烧杯超纯试剂反应杯

PFA烧杯在实验过程中可作为储酸容器或涉及强酸强碱类实验的反应容器&#xff0c;用于盛放样品、试剂&#xff0c;也可搭配电热板加热、蒸煮、赶酸用。 外壁均有凸起刻度&#xff0c;直筒设计&#xff0c;带翻边&#xff0c;便于夹持和移动&#xff0c;边沿有嘴&#xff0c;便于…

springboot+xjar加密打包部署教程

需求背景 为了跟上时代的步伐&#xff0c;为了更好的生存。开个玩笑&#xff0c;就是心血来潮&#xff0c;使用xjar加密部署jar包&#xff0c;于是就测试一下。 xjar教程 1-maven配置文件修改 首先找到自己ideal配置的maven文件夹&#xff0c;然后找到apache-maven-3.9.3\co…

C# 多线程(3)——线程池

文章目录 1 定义2 线程池使用3 安全取消线程池中任务 1 定义 线程是计算机宝贵的资源&#xff0c;频繁的创建和销毁线程将会大量的占用计算机资源&#xff08;为每个线程单独分配内存空间&#xff0c;并且多线程下的CPU时间片的切换也会耗费一定的时间&#xff09;。为了充分利…

Supplementary Influence Maximization Problem in Social Networks

本论文发表于 IEEE TRANSACTIONS ON COMPUTATIONAL SOCIAL SYSTEMS, VOL. 11, NO. 1, FEBRUARY 2024 Abstract 由于在病毒式营销中的重要应用&#xff0c;影响力最大化&#xff08;IM&#xff09;已成为一个经过充分研究的问题。它的目的是找到一小部分初始用户&#xff0c;以…

基于Python3的数据结构与算法 - 12 数据结构(列表和栈)

目录 一、引入 二、分类 三、列表 1. C语言中数组的存储方式 2. Python中列表的存储方式 四、栈 1. 栈的应用 -- 括号匹配问题 一、引入 定义&#xff1a;数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。简单来说&#x…

异常-Exception

文章目录 异常-Exception常见的运行时异常NullPointerException&#xff08;空指针异常&#xff09;ArithmeticException&#xff08;数学运算异常&#xff09;ArrayIndexOutOfBoundsException&#xff08;数组下标越界异常&#xff09;ClassCastException&#xff08;类型转换…

浏览器修改接口返回数据展示在页面上

前端自己调试&#xff0c;想修改接口返回来的数据&#xff0c;然后展示在页面上 举例 接口返回了数据&#xff0c;想要修改此数据 这时就可以修改数据了&#xff0c;修改完成保存 然后刷新页面就会使用本地保存的数据了

Linux第68步_旧字符设备驱动的一般模板

file_operations结构体中的函数就是我们要实现的具体操作函数。 注意&#xff1a; register_chrdev()和 unregister_chrdev()这两个函数是老版本驱动使用的。现在新字符设备驱动已经不再使用这两个函数&#xff0c;而是使用Linux内核推荐的新字符设备驱动API函数。 1、创建C…

“TXT文本编辑专家:一键查找,多关键字,高效办公新选择“

办公场景中&#xff0c;我们经常需要处理大量的TXT文本文件&#xff0c;从中筛选出包含特定关键字的内容。传统的文本编辑软件往往功能单一&#xff0c;无法满足多关键字、多文件的同时查找需求。现在&#xff0c;一款专为TXT文本编辑设计的办公软件应运而生&#xff0c;它将为…

ArcGIS学习(十一)公服设施服务区划分与评价

ArcGIS学习(十一)公服设施服务区划分与评价 本任务带来的内容是公服设施服务区划分与公服设施服务区评价。本任务包括两个关卡: 公服设施服务区划分公服设施服务区空间价值评价1.公服设施服务区划分 首先,来看看这个案例的场景和基础数据。我们以上海市图书馆为例进行分析…

使用docker安装运行rabbitmq---阿里云服务器

目录 0、阿里云没开端口的得要去安全组规则去添加&#xff1a; 1、下载RabbitMQ镜像&#xff1a; 2、查看镜像是否下载成功&#xff0c;得到docker镜像id&#xff1a; 3、运行RabbitMQ: 4、查看RabbbitMQ容器是否启动成功&#xff1a; 5、启动RabbitMQ中的插件管理 6、访…

微信小程序 ---- 慕尚花坊 用户管理

01. 用户登录-什么是 token 什么是 Token Token 是服务器生成的一串字符串&#xff0c;用作客户端发起请求的一个身份令牌。当第一次登录成功后&#xff0c;服务器生成一个 Token 便将此 Token 返回给客户端&#xff0c;客户端在接收到 Token 以后&#xff0c;会使用某种方式…