3 最长连续序列-北京尧图网络

给定一个未排序的整数数组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示例 3输入nums [1,0,1,2] 输出3方法1快排1、使用sort函数对nums进行排序(默认升序)nlogn。2、循环nums向量下标定义为i定义连续长度变量为k1和最大长度max_k判断nums[i]和nums[i1]是否连续。3、假如前后两个数字连续k1并且判断k是否大于max_k更新max_k。4、假如前后两个数字相等直接跳过本次循环。5、如果两个数字不连续更新k为14、持续循环nums向量直到结束返回max_k。class Solution { public: int longestConsecutive(vectorint nums) { //集合 int nnums.size(); if(n2) return n; unordered_setint mset; for(int i0;in;i){ mset.insert(nums[i]); } int k1; int max_kk; for(unordered_setint::iterator itmset.begin();it!mset.end();it){ if(mset.find(*it-1)mset.end()){ int num*it; while(1){ if(mset.find(num1)!mset.end()){ k; max_kmax_kk?max_k:k; num; }else{ k1; break; } } } } return max_k; } };方法2哈希查找1、创建一个set集合unordered_setintm_set定义连续的长度为k,最大长度为max_k。2、将nums的数全部插入m_set中。3、循环m_set容器的值定义每个值为it。4、在m_set容器中查找it的连续数字每找到一个k1更新max_k。5、循环结束返回 max_k。该方法在最坏的情况下还是会达到O(n^2)的复杂度//假如有一个连续序列{987654321} 那么一次枚举都要从最大的那个数开始枚举最坏的情况时间复杂度O(n^2)优化方法//如果已知有一个 x,x1,x2,⋯,xy 的连续序列而我们却重新从 x1x2 或者是 xy 处开始尝试匹配那么得到的结果肯定不会优于枚举 x 为起点的答案因此我们在外层循环的时候碰到这种情况跳过即可。 //由于我们要枚举的数 x 一定是在数组中不存在前驱数 x−1 的不然按照上面的分析我们会从 x−1 开始尝试匹配因此我们每次在哈希表中检查是否存在 x−1 即能判断是否需要跳过了。class Solution { public: int longestConsecutive(vectorint nums) { //集合 int nnums.size(); if(n2) return n; unordered_setint mset; for(int i0;in;i){ mset.insert(nums[i]); } int k1; int max_kk; for(unordered_setint::iterator itmset.begin();it!mset.end();it){ if(mset.find(*it-1)mset.end()){ int num*it; while(1){ if(mset.find(num1)!mset.end()){ k; max_kmax_kk?max_k:k; num; }else{ k1; break; } } } } return max_k; } };unordered_set常见函数函数作用std::unordered_setint uset;构造函数std::unordered_setint uset;插入元素uset.find(10);查找元素返回一个迭代器uset.erase(10);删除元素size_t size uset.size();返回容器的大小bool isEmpty uset.empty();判断容器是否为空uset.clear();清空容器

3 最长连续序列

相关推荐

Java大厂面经：Spring Cloud微服务+MCP+Agentic RAG三连问，水货程序员谢飞机大型翻车现场

鸿蒙 ArkTS 实战：Live Stream Script Helper 从智能助手到保存闭环完整解析

HeyGem2.0（Duix-Avatar）本地数字人整合包技术部署与使用完整教程

更多资讯

最初的梦想是通过写代码，实现自由。没想到最终会以炒股实现自由

关于java中Integer缓存数组的分析

人工智能入门 | K-means聚类算法的应用案例实战（含代码+图示）

计算机网络－概论

提示工程核心原则与AI交互设计实践

树莓派Pico低功耗实战：lightsleep深度优化与GPIO22唤醒避坑指南

今日更新

Linux 内核 ARM 虚拟内存布局全解析：从 4GB 地址空间划分到源码级验证

AIGC降重工具测评与教育应用指南

数据容灾核心指标与实战方案解析

本周精选

超人会飞不算本事：系统稳定依赖清晰规则与边界设计

超人VS蜘蛛侠：拆解超级IP的影响力与传播方法论

基于CNN的调制信号识别：MATLAB实现时频图分类实战

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？