128. Longest Consecutive Sequence

https://leetcode.com/problems/longest-consecutive-sequence/description/

solution

• sort + hash

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if not nums:
            return 0
        
        nums = list(set(nums))
        nums.sort()
        res = 1
        temp = 1
        for i in range(len(nums) - 1):
            if nums[i+1] == nums[i] + 1:
                temp += 1
                res = max(res, temp)
            else:
                temp = 1
        return res

时间复杂度：O() 空间复杂度：O()

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        nums_set = set(nums)
        res = 0
        
        for num in nums_set:
            # 如果不是一小段开始的sequence，则略过. 因为下面的while已经计算过num
            if num - 1 in nums_set:
                continue
            
            # 开始的，则寻找小段的长度
            length = 1
            while num + 1 in nums_set:
                length += 1
                num += 1
            res = max(res, length)
        return res

# 所有数字放到一个哈希表，然后不断地从哈希表中任意取一个值，并删除掉其之 前之后的所有连续数字，然后更新目前的最长连续序列长度

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if len(nums) < 2:
            return len(nums)

        nums_map = {}
        longest_consecutive = 0
        for num in nums:
            if num not in nums_map:
                nums_map[num] = [num, num]
                left = num
                right = num

                # left neighbor - extend left range
                if num - 1 in nums_map:
                    left = nums_map[num - 1][0]

                # right neighbor - extend right range
                if num + 1 in nums_map:
                    right = nums_map[num + 1][1]

                nums_map[left] = [left, right]
                nums_map[right] = [left, right]
                longest_consecutive = max(longest_consecutive, right - left + 1)

        return longest_consecutive

follow up

• 二维数组