[LeetCode] 128. Longest Consecutive Sequence_Hard tag: Hash

佚名 6年前 (2019-05-16) 随笔 2275人围观抢沙发百度已收录

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

Your algorithm should run in O(n) complexity.

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

Example:

Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

这个题目就利用hash table，python中用set来表示，s1是整个nums的hash table，s2记录visited num。然后for num in nums，每个num看看是否被visited过，其实有点DFS的思路，如果没有被visited过，将其标记为visited，然后两个while loop分别找比num大的和小的连续的数，最后将ans和count进行比较，最后返回ans即可。

Code：T: O(n), S:O(n)

class Solution:
    def longestConsecutiveSequence(self, nums: List[int]) -> int:
        ans, s1, s2 = 0, set(nums), set()
        for num in nums:
            if num in s2:
                continue
            count, temp = 1, num
            while (num + 1 in s1 and num + 1 not in s2):
                s2.add(num + 1)
                count += 1
                num += 1
            num = temp
            while (num - 1 in s1 and num - 1 not in s2):
                s2.add(num - 1)
                count += 1
                num -= 1
            ans = max(ans, count)
        return ans