209 - 128 最长连续序列

题目

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

要求算法的时间复杂度为 O(n)。

示例:

输入: [100, 4, 200, 1, 3, 2] 输出: 4 解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。

解答

难道要我先排序再找吗？😂😂

hash表

https://leetcode-cn.com/problems/longest-consecutive-sequence/solution/dong-tai-gui-hua-python-ti-jie-by-jalan/

遍历数字，然后统计在数字周围的数字，把数量加上去。

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        hash_dict = dict()
        max_length = 0
        for num in nums:
            if num not in hash_dict:
                left = hash_dict.get(num-1, 0)
                right = hash_dict.get(num+1, 0)
                cur_length = 1+left+right
                if cur_length > max_length:
                    max_length = cur_length
                hash_dict[num] = cur_length
                hash_dict[num-left] = cur_length
                hash_dict[num+right] = cur_length
        return max_length

Runtime: 68 ms, faster than 19.07% of Python3 online submissions for Longest Consecutive Sequence.

Memory Usage: 13.8 MB, less than 100.00% of Python3 online submissions for Longest Consecutive Sequence.

https://leetcode-cn.com/problems/longest-consecutive-sequence/solution/zui-chang-lian-xu-xu-lie-by-leetcode/

这个做法是把nums变成set，从最低的set开始，统计有多少个连续的

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        longest_streak = 0
        num_set = set(nums)
        for num in num_set:
            if num-1 not in num_set:
                current_num = num
                current_streak = 1
                while current_num + 1 in num_set:
                    current_num += 1
                    current_streak += 1
                longest_streak = max(longest_streak, current_streak)
        return longest_streak

Runtime: 52 ms, faster than 85.91% of Python3 online submissions for Longest Consecutive Sequence.

Memory Usage: 13.7 MB, less than 100.00% of Python3 online submissions for Longest Consecutive Sequence.