Longest Consecutive Sequence

题目描述

Given an unsorted array of integers, find the length of the longest consecutive elements 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

时间复杂度 O(nlogn)

hashtable

用空间换时间

  • 先用hashtable保存每一个num为key, value设为False

  • 然后遍历的时候，对于每一个num找上下能够达到的连续边界

    • 将用过的数在hashtable里的value设为False,这样就不会重复利用了

  • 时间复杂度 O(n)

  • 空间复杂度 O(n)

Solution

class Solution(object):
    def longestConsecutive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0
        hashMap = {}
        for num in nums:
            hashMap[num] = True

        result = 0
        for num in nums:
            if not hashMap[num]:
                continue
            curLen = 1
            k = num + 1
            while k in hashMap and hashMap[k]:
                curLen += 1
                hashMap[k] = False
                k += 1
            k = num - 1
            while k in hashMap and hashMap[k]:
                curLen += 1
                hashMap[k] = False
                k -= 1
            result = curLen if curLen > result else result

        return result

Reference