Longest Consecutive Sequence

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

Clarification

Your algorithm should run in O(n) complexity.

Example

Given [100, 4, 200, 1, 3, 2],

The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Solution

(1) 先排序在计算

It's a very tricky question, when do the sort , it's possbile to get dupliate value, it's very important to jump from the duplicate value.

0 1 1 2 3 4 5

(2) 利用哈希表来实现。

这道题利用HashSet的唯一性解决，能使时间复杂度达到O(n)。首先先把所有num值放入HashSet，然后遍历整个数组，如果HashSet中存在该值，就先向下找到边界，找的同时把找到的值一个一个从set中删去，然后再向上找边界，同样要把找到的值都从set中删掉。所以每个元素最多会被遍历两边，时间复杂度为O(n)。

class Solution:
    """
    @param num, a list of integer
    @return an integer
    """
    def longestConsecutive(self, num):
        dict = []
        longest = 0 

        for n in num:
            dict.append(n)

        for n in num:
            down = n - 1
            while down in dict:
                dict.remove(down)
                down -= 1

            up = n + 1
            while up in dict:
                dict.remove(up)
                up += 1
            longest = max(longest, up - down - 1)
        return longest