LeetCode

Appearance

128.Longest Consecutive Sequence ​

题目 ​

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

You must write an algorithm that runs in O(n) time.

 

Example 1:

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

Example 2:

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

Example 3:

Input: nums = [1,0,1,2]
Output: 3

 

Constraints:

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109
Related Topics
  • 并查集
  • 数组
  • 哈希表

  • 👍 2518
  • 👎 0

    • 解法一 ​

    通过 set 哈希表，创建步骤的时间复杂度竟然可以忽略不计。

    • 寻找序列头部，如果 num - 1 不在 set 内，则可取为序列头部
    • 寻找以头部开始，寻找最长的序列
    python
    
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        s = set(nums)
        res = 0
        # 遍历数组会造成空间浪费（数组中可能存在重复的元素）
        for i in  range(len(nums)):
            seq = 1
            if nums[i] - 1 in s:
                continue
            else:
                while nums[i] + seq in s:
                    seq += 1

            res = max(res, seq)
        return res
    • 时间复杂度O(N)
      • N = len(nums)
    • 空间复杂度O(N)

    解法二 ​

    题目中数组可能存在重复元素，因此遍历时可选用 set 为遍历的对象

    py
    from typing import List
# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        s = set(nums)
        res = 0
        # 遍历数组会造成空间浪费（数组中可能存在重复的元素）
        for num in s:
            seq = 1
            if num - 1 in s:
                continue
            else:
                while num + seq in s:
                    seq += 1

            res = max(res, seq)
        return res
# leetcode submit region end(Prohibit modification and deletion)

Solution().longestConsecutive([100,4,200,1,3,2])

    复杂度分析 ​

    • 时间复杂度O(N)
      • N = size of set <= length of nums
    • 空间复杂度O(N)