[python 刷题] 128 Longest Consecutive Sequence
[python 刷题] 128 Longest Consecutive Sequence
题目:
Given an unsorted array of integers
nums
, return the length of the longest consecutive elements sequence.You must write an algorithm that runs in
O(n)
time.
这题给了一个没有排序的数组,并且要求找出最长的连续序列
最简单的方式其实还是排序,不过题目中要求时间复杂度为 O ( n ) O(n) O(n),而排序的时间复杂度为 O ( n l o g ( n ) ) O(n log(n)) O(nlog(n))
Union Find 也可以用来解这题,它的时间复杂度是 amortized linear,不过这个问题的话有一个 linear 的解。
以 [100,4,200,1,3,2]
为例,假设有一个无限延长的 x 轴,所有的点在 x 轴上看起来是这个样子的:
这个情况下就比较清楚的可以看到哪个点在哪个 cluster 里,在实际的实现中,可以用一个 set 去存储所有出现的值,每次将值存入 cluster 中,都可以检查一下当前值是否是 cluster 的最小值,如果是的话,查看当前 cluster 的长度
代码如下:
class Solution:def longestConsecutive(self, nums: List[int]) -> int:num_set = set(nums)max_len = 0for num in num_set:if (num - 1) in num_set:continuelocal_max = 1right = num + 1while right in num_set:local_max += 1right += 1max_len = max(max_len, local_max)return max_len
整体时间复杂度的分析:
创建 set 的时间复杂度为 O ( n ) O(n) O(n)
第一个 for
循环的时间复杂度为 O ( n ) O(n) O(n),
查询当前值是否存在与 set 的时间复杂度为 O ( 1 ) O(1) O(1)
第二个循环 while
在最差的情况下会跑 O ( n ) O(n) O(n) 次,但是因为有 if
,的检查,所以这个情况最坏只会跑一次,而 O ( n + n ) O(n + n) O(n+n) 在大 O 里面依旧是 O ( n ) O(n) O(n),所以整体的时间复杂度为 O ( n ) O(n) O(n)