128_longest_consecutive_sequence.py

'''
Author: Zhiwei Zhu (zhuzhiwei21@zju.edu.cn)
Date: 2025-09-11 14:41:28
LastEditors: Zhiwei Zhu (zhuzhiwei21@zju.edu.cn)
LastEditTime: 2025-09-11 15:09:28
FilePath: /LeetCodePython/longest_consecutive_sequence.py
Description: 

Copyright (c) 2025 by Zhiwei Zhu, All Rights Reserved. 
'''
from typing import List

# O(n) solution using hash set
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        num_set = set(nums)
        max_length = 0
        for num in num_set:
            if num - 1 not in num_set:  # only start counting if `num` is the start of a sequence
                cur_num = num
                cur_length = 1
                while cur_num + 1 in num_set:
                    cur_num += 1
                    cur_length += 1
                max_length = max(max_length, cur_length)
        return max_length


# zzw
'''
总体时间复杂度
排序操作：O(nlogn)
遍历数组：O(n)
由于 O(nlogn) 是主导项，因此整个算法的时间复杂度是 O(nlogn)。
'''
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        nums = sorted(nums)
        max_length = 0
        cur_length = 0
        for i, num in enumerate(nums[:-1]):
            if nums[i + 1] - num == 1:
                cur_length += 1
            elif nums[i + 1] - num == 0:
                continue
            else:
                if cur_length > max_length:
                    max_length = cur_length
                cur_length = 0
        if cur_length > max_length:
            max_length = cur_length
        return max_length + 1
    
nums = [0,3,7,2,5,8,4,6,0,1]
print(Solution().longestConsecutive(nums))
nums = [100,4,200,1,3,2]
print(Solution().longestConsecutive(nums))
nums = [1,2,0,1]
print(Solution().longestConsecutive(nums))
nums = []
print(Solution().longestConsecutive(nums))