【LeetCode最详尽解答】128_最长连续序列 Longest-Consecutive-Sequence

欢迎收藏Star我的Machine Learning Blog:https://github.com/purepisces/Wenqing-Machine_Learning_Blog。如果收藏star, 有问题可以随时与我交流, 谢谢大家！

链接:

• 128_最长连续序列

直觉

• 输入: nums = [100, 4, 200, 1, 3, 2]
• 输出: 4
• 解释: 最长的连续元素序列是 [1, 2, 3, 4]。因此它的长度是 4。

首先，我们需要找到每个递增序列的起始位置，并且舍弃重复的值。所以先使用 set(nums) 将 nums 转换为一个集合。集合中的每个值可能是起始位置，也可能只是序列的一部分。我们只需要找到起始值。

考虑列表 [1, 2, 3, 4, 5, 6]。如果不只找起始点，它会计算从 1-6，2-6，3-6 等开始的序列，导致 $(O(n^2)$ 的复杂度。为了确保线性时间复杂度，我们需要仅识别每个间隔的起始点。

当遇到一个值时，如果 n-1 在集合中，跳过它，因为它不是起始位置。如果 n-1 不在集合中，说明 n 是一个起始值，我们将长度初始化为 1。当 n + length 在集合中时，长度加 1。然后，将结果更新为 length 和当前结果中的最大值。

方法

我们将找到每个起始位置，并使用哈希集合存储 nums 的所有值。当我们找到一个起始位置时，我们将从这个位置计算序列的长度。然后，更新最终结果并返回它。

找到起始位置:

• 如果 n-1 不在 numset 中，那么 n 是一个起始位置。
• 将长度初始化为 1。
• 当 n + length 在 numset 中时，我们增加长度。
• 最后，用找到的最长长度更新结果。

复杂度

• 时间复杂度:
  $$O(n)$$

  • 创建集合: $O(n)$
  • 遍历列表: $O(n)$
  • 检查序列的起始点并计算长度: $O(n)$

• 空间复杂度:
  $$O(n)$$

  • 集合的空间: $O(n)$
  • 其他变量的空间: $O(1)$

代码

class Solution(object):
    def longestConsecutive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        numset = set(nums)
        longest = 0
        for n in nums:
            # calculate just from the starting position
            if n-1 not in numset:
                length = 1
                while n + length in numset:
                    length+=1
                longest = max(longest, length)
        return longest