LeetCode #128：最长连续序列

1970-01-01 00:00 (GMT+8) 阅读时间 0 分钟 面试算法LeetCodeLeetCode-MediumPython哈希表并查集数组

https://leetcode.cn/problems/longest-consecutive-sequence/description/

题目分析

先把模板套上，求最长和最大问题，一般就是先维护一个当前值 current，一个最大值 max，然后用 max(current, max) 来更新最大值。又因为这题要求 $O(n)$ 的时间复杂度，所以不能直接排序（排序一上来最好就是 $O(n\log n)$）。根据数组问题先无脑上哈希表的原则，这题可以先用哈希表去一下重。

又因为如果一个元素 $n$ 自己在最长连续序列里（并且不是第一个）的话，那么他的前一个元素 $n-1$ 一定在哈希表里，所以我们可以从 $k$ 开始，不断向前找，直到找到一个$k-1$ 不在哈希表里的元素，这样就可以找到以 $k$ 为起始值的元素作为最长了连续序列的头元素。

题解

注意循环是在去重集合中循环，而不是在原数组中循环。原数组中可能有大量重复的数，第一遍我就是这样 TLE 的。

Python

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        longest =0
        current_num = 0
        current = 0
        dedup = set(nums)

        for num in dedup:
            if not num - 1 in dedup:
                current_num = num
                current = 1

                while current_num + 1 in dedup:
                    current_num += 1
                    current += 1

                longest = max(longest, current)

        return longest

页面历史

最后编辑于 6 天前

查看完整历史

f88333f-docs: 添加 LeetCode #128 - 最长连续序列 题解