leetcode_128_最长连续序列

最长连续序列

描述

困难

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

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

示例:

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

解题

一开始的想法是，利用字典保存数据，以数组中的数为键，其长度为值（具体看代码）

遍历每个数，如果这个数的前一个数存在于字典之中，在字典中这个数的值为其前一个数的值加1

否则，这个数的值为1

然后判断这个数的后面的连续的数是否在数组中，如果存在，更新字典

但是，超时了

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        nums_set = set(nums)
        nums_dic = {}

        longest_length = 0

        for num in nums:
            # 如果其前一个数存在于字典中
            if num - 1 in nums_dic:
                nums_dic[num] = nums_dic[num - 1] + 1
            else:
                nums_dic[num] = 1
            # 判断这个数后面的连续的数是否存在于数组中
            while num + 1 in nums_set:
                nums_dic[num + 1] = nums_dic[num] + 1
                num += 1

            longest_length = max(longest_length, nums_dic[num])

        return longest_length

仍然是遍历每个数，判断这个数的前一个数是否存在于数组中

如果不存在，那么就设置当前长度为1，然后获得以这个数为起始的最长长度，最后比较获得答案

由于代码只判断前一个数是否存在于数组中，进入if语句的数字仅仅是各个连续序列的起始数据

效率得到了极大的提高

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        nums_set = set(nums)
        longest_length = 0

        for num in nums:
            if num - 1 not in nums_set:
                cur = 1		# 用于计算当前连续序列的长度
                while num + 1 in nums_set:
                    num += 1
                    cur += 1
                longest_length = max(longest_length, cur)

        return longest_length