LC128.最长连续序列

1.题目

• 128. 最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为O(n) 的算法解决此问题。

示例 1：

**输入：** nums = [100,4,200,1,3,2]
**输出：** 4
**解释：** 最长数字连续序列是 `[1, 2, 3, 4]。它的长度为 4。

示例 2：

**输入：** nums = [0,3,7,2,5,8,4,6,0,1]
**输出：** 9

提示：

• 0 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9

2. 思路

2.1 哈希表

• 维护一个哈希表，mp[num] = true 表示数据出现过
• 首先，将这个数组全部放进去
• 然后，遍历哈希表，如果 num - 1 存在，那么就是说明当前的 num 不是开头第一个元素，就 continue 掉。
• 如果 num - 1 不存在，说明当前的 num 是开头元素，那么另外开一个 for 循环，看当前序列的长度。

2.2 并查集

• 思路更加直观，维护一个并查集，将数值相邻的元素放进去。
• 看并查集当中最大的一坨有多大，它的规模就是答案。

3.代码

3.1 哈希表

func longestConsecutive(nums []int) int {
    mp := make(map[int]bool)

    for _, v := range nums {
        mp[v] = true
    }

    ans := 0
    for num := range mp {
        // current must be the first element
        if mp[num - 1] {
            continue
        }

        cnt := 0
        cur := num
        for mp[cur] {
            cur++
            cnt++
        }
        ans = maxx(ans, cnt)
    }

    return ans
}

func maxx(nums ...int) int {
    res := nums[0]
    for _, num := range nums {
        if num > res {
            res = num
        }
    }
    return res
}

3.2 并查集

type unionFind struct {
    fa map[int]int
    size map[int]int
}

func (uf *unionFind) find(x int) int {
    if uf.fa[x] != x {
        uf.fa[x] = uf.find(uf.fa[x])
    }
    return uf.fa[x]
}

func (uf *unionFind) merge(x int, y int) {
    rx, ry := uf.find(x), uf.find(y)
    if rx != ry {
        uf.fa[rx] = ry
        uf.size[ry] += uf.size[rx]
    }
}

func longestConsecutive(nums []int) int {
    // n := len(nums)

    uf := &unionFind {
        fa : map[int]int{},
        size : map[int]int{},
    }

    ans := 0
    for _, num := range nums {
        if _, has := uf.fa[num]; has {
            continue
        }

        uf.fa[num] = num
        uf.size[num] = 1

        if _, has := uf.fa[num - 1]; has {
            uf.merge(num - 1, num)
        }

        if _, has := uf.fa[num + 1]; has {
            uf.merge(num, num + 1)
        }

        curSize := uf.size[uf.find(num)]
        if curSize > ans {
            ans = curSize
        }
    }

    return ans
}