2021-04-18：给定一个二维数组matrix，里面的值不是1就是0，上、下、左、右相邻的1认为是一片岛，返回m

2021-04-18：给定一个二维数组matrix，里面的值不是1就是0，上、下、左、右相邻的1认为是一片岛，返回matrix中岛的数量。

福大大 答案2021-04-18：

并查集。

代码用golang编写。代码如下：

package main

import "fmt"

func main() {
    arr := [][]byte{
        {49, 49, 49, 49, 48},
        {49, 49, 48, 49, 48},
        {49, 49, 48, 49, 48},
        {49, 49, 48, 48, 48},
        {48, 48, 48, 48, 48}}
    ret := numIslands(arr)
    fmt.Println(ret)
}
func numIslands(board [][]byte) int {
    row := len(board)
    col := len(board[0])
    uf := NewUnionFind(board)
    for j := 1; j < col; j++ {
        if board[0][j-1] == '1' && board[0][j] == '1' {
            uf.union(0, j-1, 0, j)
        }
    }
    for i := 1; i < row; i++ {
        if board[i-1][0] == '1' && board[i][0] == '1' {
            uf.union(i-1, 0, i, 0)
        }
    }
    for i := 1; i < row; i++ {
        for j := 1; j < col; j++ {
            if board[i][j] == '1' {
                if board[i][j-1] == '1' {
                    uf.union(i, j-1, i, j)
                }
                if board[i-1][j] == '1' {
                    uf.union(i-1, j, i, j)
                }
            }
        }
    }
    return uf.getSets()
}

type UnionFind2 struct {
    parent []int
    size   []int
    help   []int
    col    int
    sets   int
}

func NewUnionFind(board [][]byte) *UnionFind2 {
    ret := &UnionFind2{}
    ret.col = len(board[0])
    ret.sets = 0
    row := len(board)
    length := row * ret.col
    ret.parent = make([]int, length)
    ret.size = make([]int, length)
    ret.help = make([]int, length)
    for r := 0; r < row; r++ {
        for c := 0; c < ret.col; c++ {
            if board[r][c] == '1' {
                i := ret.index(r, c)
                ret.parent[i] = i
                ret.size[i] = 1
                ret.sets++
            }
        }
    }
    return ret
}

// (r,c) -> i
func (this *UnionFind2) index(r int, c int) int {
    return r*this.col + c
}

// 原始位置 -> 下标
func (this *UnionFind2) find(i int) int {
    hi := 0
    for i != this.parent[i] {
        this.help[hi] = i
        hi++
        i = this.parent[i]
    }
    for hi--; hi >= 0; hi-- {
        this.parent[this.help[hi]] = i
    }
    return i
}

func (this *UnionFind2) union(r1 int, c1 int, r2 int, c2 int) {
    i1 := this.index(r1, c1)
    i2 := this.index(r2, c2)
    f1 := this.find(i1)
    f2 := this.find(i2)
    if f1 != f2 {
        if this.size[f1] >= this.size[f2] {
            this.size[f1] += this.size[f2]
            this.parent[f2] = f1
        } else {
            this.size[f2] += this.size[f1]
            this.parent[f1] = f2
        }
        this.sets--
    }
}

func (this *UnionFind2) getSets() int {
    return this.sets
}

执行结果如下：

左神java代码
力扣200. 岛屿数量