↓Skip to main content
  1. Posts/

LeetCode-128 最长连续序列

·1 min·
Table of Contents

LeetCode-128 最长连续序列 #

Solution 1 #

要求找出数字连续的最大集合, 等价于将相差 1 的节点连上边, 寻找最大的连通子图, 这可以通过并查集来实现. 代码如下:

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        nums = set(nums)
        ans = 0

        fa = {num: num for num in nums}
        size = {num: 1 for num in nums}
        
        def find(x):       
            if fa[x] != x:
                fa[x] = find(fa[x])
            return fa[x]

        def merge(x, y):
            x = find(x)
            y = find(y)
            if x != y:
                fa[x] = y
                size[y] += size[x]
        
        for num in nums:
            if num + 1 in fa:
                merge(num, num + 1)
        if size:
            ans = max(size.values())
        return ans