【最长连续序列】python刷题记录

目录

并查集

初始化：

 find函数

union函数

并查集的优化：

思路：

代码： 

结果：

 ps:

重大调整PS:

调整一下刷题顺序，之前是按照模块，但现在觉得模块太单调了，决定每个=次循环都抽取模块中的一道中等题来刷，毕竟算法都学过。

难点：O(n)复杂度，所以直接拿去排序不太行

并查集

并查集_哔哩哔哩_bilibili

初始化：

创建parent数组，每一个i点对应的值都是其父节点 

 find函数

--------查找parent数组直到-1返回i（集合树的根）

union函数

例如union(3,6)

先find(3),再find(6)，如果r1!=r2，那么将parent数组中的r2的parent赋值为r1

并查集的优化：

把同一个parent单路上的parent修改为root

例如左图单路修改后为右图所示

思路：

将每个数字看成一个节点，连接的关系就是数值比他大1。即可以看成是求满足条件建树的最大树的节点个数。

代码：

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        #相同元素没有意义，可以舍弃
        nums=set(nums)
        ans=0

        #并查集
        #值为离散的，使用字典
        #准备用做parent字典
        fa={num:num for num in nums}
        #对于每个数字来说，以它开始的最长连续初始都为1
        size={num:1 for num in nums}

        def find(x):
            if fa[x]!=x:
                fa[x]=find(fa[x])
            return fa[x]
        
        def union(f,to):
            f=find(f)
            to=find(to)
            if f!=to:
                fa[f]=to
                size[to]+=size[f]

        #遍历数组，满足union时，取max
        for num in nums:
            if num+1 in fa:
                union(num,num+1)
        #size.values()当size是字典是能取所有的值出来
        if size:
            ans=max(size.values())
        return ans

结果：

 ps:

size.values()当size是字典是能取所有的值出来

感谢伪灵神！！