[LeetCode]128. 最长连续序列(Longest Consecutive Sequence)

题目描述

给定一个未排序的整数数组,找出最长连续序列的长度。

要求算法的时间复杂度为 O(n)。

示例:

输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。

解题思路

使用 Python 中的 set 数据结构,本质实现为 hashmap,获取、修改、删除的平均时间复杂度都为 O(n)
遍历 set,若当前数字 num 的前一个数字 num-1 不在 set 中,则说明当前数字为一个连续序列的起始数字,从当前数字开始 +1,并计算最大能够连续的长度。
整个过程的时间复杂度为 O(n)
while 循环在整个过程中只会被迭代 n 次,因为起始数字(while 循环开头)+非起始数字(while 循环内)=n。

代码

Python 3.6

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
max_length = 0
hash_set = set(nums)
for num in hash_set:
if num - 1 not in hash_set:
cur_length = 1
while num + 1 in hash_set:
cur_length += 1
num += 1
max_length = max(max_length, cur_length)
return max_length

执行用时:84 ms
内存消耗:15.1 MB