leetcode--python--hot100--128

最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度

注意重复元素的情况，第一种方法中用same表示元素重复的数量;方法一时间复杂度为排序的复杂度，方法二为o（n）

class Solution(object):
    def longestConsecutive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums.sort()
        i, n, max_length = 0, len(nums), 0
        while i < n:
            start = i
            same = 0
            while i < n - 1 and nums[i+1] - nums[i] <= 1:
                if nums[i+1] == nums[i]:
                    same += 1
                i += 1
            max_length = max(i - start + 1 - same, max_length)
            i += 1
        return max_length

        num_unique = set(nums)
        max_length = 0
        for num in num_unique:
            if num - 1 not in num_unique:
                cur_num = num
                cur_length = 1
                while cur_num + 1 in num_unique:
                    cur_length += 1
                    cur_num += 1
                max_length = max(max_length, cur_length)
        return max_length