LeetCode--128--最长连续序列(python)
2020-12-13 13:40
标签：时间 nbsp for 复杂 一个 数字 else 部分 python 给定一个未排序的整数数组，找出最长连续序列的长度。 要求算法的时间复杂度为 O(n)。 示例: 输入: [100, 4, 200, 1, 3, 2] 暴力超时。。。 先排序，在有序list中，判断前一个数字是否比后一个少1，注意最后一个可能是最长连续序列的一部分，所以最后要再比一次 LeetCode--128--最长连续序列(python) 标签：时间 nbsp for 复杂 一个 数字 else 部分 python 原文地址：https://www.cnblogs.com/NPC-assange/p/11531443.html
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
longestSequence = 0
for num in nums:
curNum = num
streak = 1
while curNum +1 in nums:
curNum += 1
streak += 1
longestSequence = max(longestSequence,streak)
return longestSequence
1 class Solution:
2 def longestConsecutive(self, nums: List[int]) -> int:
3 if not nums:
4 return 0
5 nums.sort()
6 longestSequence = 1
7 curStreak = 1
8 for i in range(1,len(nums)):
9 if nums[i] != nums[i-1]:
10 if nums[i] == nums[i-1]+1:
11 curStreak += 1
12 else:
13 longestSequence = max(longestSequence,curStreak)
14 curStreak = 1
15 return max(longestSequence, curStreak)
文章标题：LeetCode--128--最长连续序列(python)
文章链接：http://soscw.com/essay/33165.html