128. 最长连续序列【并查集】

题目

题目

思路

并查集

代码

package main

import (
    "bytes"
    "fmt"
)

// 给定一个未排序的整数数组，找出最长连续序列的长度。
// 要求算法的时间复杂度为 O(n)。
//
// 输入: [100, 4, 200, 1, 3, 2]
// 输出: 4
// 解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。
//
// 思路：连通性问题，并查集；（一个方向上进行合并）（100和99）（4和3）（200和199）（1和0）（3和2）（2和0）
//      求集合个数，并查集里填写集合个数
//
func longestConsecutive(nums []int) int {
    ufs := NewUnionFindSet(nums)
    //fmt.Printf("before ufs is %v\n\n", ufs)

    // [0, 0, -1]，重复的只处理1遍！
    processedMap := make(map[int]bool)
    for _, num := range nums {
        if _, ok := processedMap[num]; !ok {
            ufs.Union(num, num-1)
            processedMap[num] = true
        }
    }
    //fmt.Printf("after ufs is %v\n\n", ufs)

    res := 0
    for k, v := range ufs.Set {
        if k == v[0] && v[1] > res {
            res = v[1]
        }
    }

    return res
}

// 构造一个ufs
type UnionFindSet struct {
    Set map[int]*[2]int   // key是元素，value[0]是父节点，value[1]是集合元素个数
}

func NewUnionFindSet(nums []int) *UnionFindSet {
    ufs := &UnionFindSet{Set: make(map[int]*[2]int)}
    for _, v := range nums {
        // [0, 0, -1]，重复的不要
        if _, ok := ufs.Set[v]; !ok {
            ufs.Set[v] = &[2]int{v, 1}
        }
    }
    return ufs
}

// find，查找元素i的主人，并在此过程中，将自己主人的值为最顶层的主人
func(ufs *UnionFindSet) FindRoot(x int) int {
    if ufs.Set[x][0] != x { // 自己不是顶层root
        // 为什么非指针的话，赋不了值
        ufs.Set[x][0] = ufs.FindRoot(ufs.Set[x][0]) // 找到自己父节点的root，置到自己的父节点（还不是root）
        // 1、元素个数，确保了集合总数都在根节点上
        ufs.Set[ufs.Set[x][0]][0] += ufs.Set[x][1]
        ufs.Set[x][1] = 0
    }

    return ufs.Set[x][0] // 返回自己的父节点(已经为root了)
}

// union： 合并元素x和元素y
// 合并后，Value存储的不一定是root，最后一次的时候，全部FindRoot一下？
func(ufs *UnionFindSet) Union(x, y int) {
    // 可能不存在
    _, okx :=ufs.Set[x]
    _, oky :=ufs.Set[y]

    if !okx || !oky {
        return
    }

    rootX := ufs.FindRoot(x)
    rootY := ufs.FindRoot(y)

    if rootX > rootY {
        rootX, rootY = rootY, rootX
    }

    // rootX < rootY
    ufs.Set[rootY][0] = rootX
    // 2、元素个数，确保了集合总数都在根节点上
    ufs.Set[rootX][1] += ufs.Set[rootY][1]
    ufs.Set[rootY][1] = 0
}

func(ufs *UnionFindSet) String() string {
    var strBuf bytes.Buffer
    strBuf.WriteString("UFS:<\n")
    for k,v := range ufs.Set {
        strBuf.WriteString(fmt.Sprintf("%v:[根节点：%v, 集合个数：%v]\n", k, v[0], v[1]))
    }
    strBuf.WriteString(">\n")
    return strBuf.String()
}

结果

结果