[Leetcode 128] 最长连续序列

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

解法一:排序 + 一次遍历

通过排序,把连续的数字排列在一起,然后一遍扫描就能找到最长连续段。
notion image
复杂度
  • 时间: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存在,就把xx+1 在一起;
最终答案是最大连通分量的大小。
因为数字可能很大,连续序列不一定从0开始,所以需要用哈希表来把“数字值”映射成并查集的节点。
复杂度
  • 时间:O(n α(n)) ≈ O(n)
  • 空间:O(n),存储父节点与集合大小
 
上一篇
[Leetcode 126] 单词接龙 II
下一篇
[Leetcode 138] 随机链表的复制