Longest Consecutive Sequence

Question

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

Example

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

Clarification Your algorithm should run in O(n) complexity.

Thoughts

主要要注意的有几点

• unsorted
• may have duplicate numbers

python做法很简单，先sort(不知道允许不允许……)，然后一个个check是否相等或比之前一个大1,DP

Solution

class Solution:
    """
    @param num, a list of integer
    @return an integer
    """
    def longestConsecutive(self, num):
        # write your code here
        num.sort()
        max = 1
        lNum = [ 1 for i in range(len(num))]
        for i in range(1, len(num)):
            if num[i] == num[i-1] + 1:
                lNum[i] = lNum[i-1] + 1
                if max < lNum[i]:
                    max = lNum[i]
            elif num[i] == num[i-1]:
                lNum[i] = lNum[i-1]
        return max