type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
给定一个未排序的整数数组
nums,找出连续数字的最长序列的长度。注:序列元素不需要在原数组中连续。
请设计并实现时间复杂度为
O(n)的算法解决此问题。示例 1:
示例 2:
示例 3:
解法一:排序 + 一次遍历
通过排序,把连续的数字排列在一起,然后一遍扫描就能找到最长连续段。

复杂度
- 时间:O(n log(n))排序, 不符合
O(n)的时间复杂度要求。
- 空间:O(1)
解法二:哈希表 (推荐)
我们把所有数字都放进一个集合
set 里,这样我们能在 O(1) 时间判断某个数是否存在。我们不从每个数都开始数,而是只从连续序列的起点开始数。
“起点”的判断:当
x - 1 不在集合中时,x 就是某个连续序列的开头。从这个
x 开始,不断地往上加:x+1, x+2, x+3...,直到下一个数不存在为止。复杂度
- 时间:
O(n)每个数字最多被访问两次(一次作为起点判断,一次在向上数的过程中)
- 空间:
O(n)(集合)
解法三:并查集
把每个数看作一个点,若
x+1存在,就把x和x+1 并在一起;最终答案是最大连通分量的大小。
因为数字可能很大,连续序列不一定从0开始,所以需要用哈希表来把“数字值”映射成并查集的节点。
复杂度
- 时间:O(n α(n)) ≈ O(n)
- 空间:O(n),存储父节点与集合大小
- Author:Fan Luo
- URL:https://fanluo.me/article/leetcode-128-最长连续序列
- Copyright:All articles in this blog adopt BY-NC-SA agreement. Please indicate the source!
上一篇
[Leetcode 126] 单词接龙 II
下一篇
[Leetcode 138] 随机链表的复制