【Leetcode】【python】Longest Consecutive Sequence 最长连续序列

题目大意

给定一组无序的整数,找出其中连续整数的最长长度。
注意点:
算法时间复杂度为O(n)

解题思路

哈希表,遍历每个数,从中间扩展左右两边,不断刷新最长长度

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
def longestConsecutive(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
numset, maxlen = set(nums), 0
for n in set(nums):
currlen = 1

tmp = n + 1
while tmp in numset:
currlen += 1
numset.discard(tmp) # 删去
tmp += 1

tmp = n - 1
while tmp in numset:
currlen += 1
numset.discard(tmp)
tmp -= 1
maxlen = max(maxlen, currlen)
return maxlen

总结