leetcode解题报告(5):Longest Consecutive Sequence
2024-08-27 15:18:14
描述
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example, Given [100, 4, 200, 1, 3, 2], The longest consecutive elements sequence is [1,
2, 3, 4]. Return its length: 4.Your algorithm should run in O(n) complexity.
分析
对于这类题目,我们最自然的想法就是先排序,再对每一个数据进行处理。但是最常用的排序算法快速排序的平均运行时间也有O(nlgn),插入排序在最好的情况下才能达到O(n)的复杂度。
因此,这题不能用“先排序,再处理”的思路,可以考虑使用哈希表unordered_map<int,bool>。
该map记录每个元素是否被使用,对每个元素,以该元素为中心,分别向两边扩张,并记录扩张的长度,直到不连续时为止。
如:考察数组 [100, 4, 200, 1, 3, 2],从第一个元素(100)开始遍历每一个元素,分别查找向左(减一)和向右(加一)后的元素是否在该数组中,若在数组中,则将长度加一,同时将bool值置为true,以表示“该元素已和数组中的另一元素连续,不必再对该元素进行处理”。否则,退出循环。
这样,我们就能得到每一个元素的最大长度,只要在每一次遍历后更新最大长度就可以了。
代码如下:
class Solution{
public:
int longestConsecutive(const vector<int>&nums){
int longest = 0; //record the longest consecutive
unordered_map<int,bool>used;
for(auto num : nums){
int length = 1;
used[num] = true;
for(int next = num + 1; used.find(next) != used.end(); ++next){
used[next] = true;
++length;
}
for(int pre = num - 1; used.find(pre) != used.end(); --pre){
used[pre] = true;
++length;
}
longest = max(longest,length);
}
return longest;
}
};
最新文章
- 理解Docker(5):Docker 网络
- Android开发环境搭建
- mssql数据库添加,修改,删除字段
- 复旦大学2015--2016学年第一学期高等代数I期末考试情况分析
- jquery简单原则器(匹配索引为指定值的元素)
- 【bzoj1497】 NOI2006—最大获利
- 成功获取并更改中兴F660光猫的超级用户密码解除四台限制
- 硝烟中的Scrum和XP-我们如何实施Scrum 4 (Part 1/2)
- SEO分享:我为什么会有这么多的优质外链资源?
- 在Android上仿百度贴吧客户端Loading图标小球
- NOIP2017SummerTraining0714
- Java进阶篇设计模式之七 ----- 享元模式和代理模式
- Android Studio 中 Live Templates 的使用
- Python之jinja2
- (简单)华为Nova3 PAR-AL00的USB调试模式在哪里开启的步骤
- JS 面向对象 ~ 创建对象的 9 种方式
- django -- 修改admin 密码问题
- EF动态linq的两种方式
- voltdb数据库持久性,扩展集群
- EM算法(Expectation Maximization Algorithm)