Longest Consecutive sequence

题目描述

For example, Given [100, 4, 200, 1, 3, 2], The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4. Your algorithm should run in O(n) complexity.

解题方法

brute force的方法

sort然后遍历找连续的sequence

空间换时间

1. 将出现过的数存到hashtable里
2. 对每一个数，进行左右的最大探索找到范围

Solution

class Solution(object):
    def longestConsecutive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        length = len(nums)
        if length == 1:
            return 1
        num_map = {}
        max_len = 1

        for num in nums:
            num_map[num] = True

        for num in nums:
            if num_map[num] == False:
                continue
            curLen = 1
            # left
            k = num - 1
            while k in num_map and num_map[k]:
                curLen += 1
                num_map[k] = False
                k -= 1
            # right
            k = num + 1
            while k in num_map and num_map[k]:
                curLen += 1
                num_map[k] = False
                k += 1
            max_len = max(curLen, max_len)

        return max_len

Reference