My Python Disjoint-Set


  • 0
    class Solution(object):
        def longestConsecutive(self, nums):
            dic = {}
            for num in  nums:
                dic[num] = num
            def find(a):
                if a == dic[a]:
                    return a
                else:
                    dic[a] = find(dic[a])
                    return dic[a]
            def union(a, b):
                ra, rb = find(a), find(b)
                dic[ra] = rb
            for num in nums:
                if num - 1 in dic:
                    union(num - 1, num)
                if num + 1 in dic:
                    union(num, num + 1)
            ans = 1
            for num in nums:
                ans = max(ans, find(num) - num + 1)
            return ans
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.