124. 最长连续序列

124. 最长连续序列

中文English

给定一个未排序的整数数组，找出最长连续序列的长度。

样例

样例 1

输入 : [100, 4, 200, 1, 3, 2]
输出 : 4
解释 : 这个最长的连续序列是 [1, 2, 3, 4]. 返回所求长度 4

说明

要求你的算法复杂度为O(n)

class Solution:
    """
    @param num: A list of integers
    @return: An integer
    """
    '''
    大致思路：
    1.先排序，然后判断下一位是否大于当前，如果大于c += 1,否则c重置，最终返回m
    '''
    def longestConsecutive(self, num):
        num.sort()
        num.append(min(num)-1)
        c = 1
        m = 0
        for i in range(len(num)-1):
            if num[i+1] == num[i]:
                continue
            if num[i+1] == num[i] + 1:
                c += 1 
            else:
                if c > m:
                    m = c
                c = 1
        return  m