【LeetCode每天一题】Longest Consecutive Sequence(最长的连续序列

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Your algorithm should run in O(n) complexity.

Example:

Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1,2,3,4] 
Therefore its length is 4.


思路

  这道题求列表中的最长连续序列,因为是列表无序的,因此我们最简单的方法就是先将列表排序,然后从头到尾进行遍历查找。找出最长子序列。这种算法的时间复杂度为O(nlogn),空间复杂度为O(1)。还有另外一种方法就是我们利用python中集合的特性,先将列表转化成集合除去其中重复的元素,然后从头开始进行遍历离查找。这种解法的时间复杂度为O(n),(为什么会是n?因为我想起了一个复杂度分析中的均摊法,在操作的过程中大部分操作都是O(1),只有一个是O(n2),所以均摊下来的话就是O(n)。)
解决代码

第一种解法
 1 class Solution(object):
 2     def longestConsecutive(self, nums):
 3         """
 4         :type nums: List[int]
 5         :rtype: int
 6         """
 7         if not nums or len(nums) == 1:    # 异常情况,直接返回
 8             return 0 if not nums else 1
 9         nums.sort()           # 先排序
10         # nums = list(set(nums))
11         max_leng = 0       # 结果变量
12         cur_leng = 1       # 记录当前的长度
13         for i in range(1, len(nums)):     # 从头开始遍历。
14             if nums[i] == nums[i-1]:      # 重复的直接遍历下一个
15                 continue
16             if nums[i] == nums[i-1]+1:    #  判断前一个和当前的这个是否是连续
17                 cur_leng += 1
18             else:                         # 记录结果
19                 max_leng = max(max_leng, cur_leng)     
20                 cur_leng = 1
21         return max(max_leng, cur_leng)     # 返回当前的结果
第二种解法
 1 class Solution(object):
 2     def longestConsecutive(self, nums):
 3         """
 4         :type nums: List[int]
 5         :rtype: int
 6         """
 7         if not nums or len(nums) == 1:
 8             return 0 if not nums else 1        
 9         nums_set = set(nums)      # 转化为集合,去除重复的元素
10         max_leng = 0
11         for i in nums_set:    
12             if i-1 not in nums_set:   # 判断该当前元素减一,是否在集合中。 如果不存在的话,那就从当前元素进行查找,找到以当前元素开始最长的序列.
13                 cur_nums = i
14                 cur_leng = 1
15                 while cur_nums +1 in nums_set:   
16                     cur_nums += 1
17                     cur_leng += 1
18                 max_leng = max(max_leng, cur_leng)  # 得到当前元素最长的连续序列
19         return max_leng         # 返回结果
原文地址:https://www.cnblogs.com/GoodRnne/p/10919765.html