题目描述（中等难度）

一个二维数组，把 看做陆地，把 0 看做大海，陆地相连组成一个岛屿。把数组以外的区域也看做是大海，问总共有多少个岛屿。

解法一

想法很简单，我们只需要遍历二维数组，然后遇到 1 的时候，把当前的 1 以及它周围的所有 1 都标记成一个字符，这里直接标记成 2。然后记录遇到了几次 1，就代表有几个岛屿。看下边的例子。

还有一个问题就是怎么标记与当前 相邻的 1。也很直接，我们直接把和当前 1 连通的位置看做一个图，然后做一个遍历即可。可以直接用递归写一个 DFS，即深度优先遍历。

当然做遍历的话，我们也可以采用 BFS，广度优先遍历。图的广度优先遍历和二叉树的 类似，只需要借助一个队列即可。

和上边的区别不大，改一下标记函数即可。

此外入队列的时候，我们把二维坐标转为了一维，就省去了再创建一个类表示坐标。

解法二 并查集

一开始看到这道题，我其实想到的是并查集，然后想了想感觉有些复杂，复杂度可能会高一些，就换了下思路想到了解法一。逛了一下 Discuss 发现也有人用并查集实现了，那这里也再总结下。

看下维基百科对 并查集 的定义。

网上很多讲并查集的文章了，这里推荐 ，大家可以先去看一下。

知道了并查集，下边就很好解决了，因为你会发现，我们做的就是分类的问题，把相邻的 1 都分成一类。

首先我们把每个节点各作为一类，用它的行数和列数生成一个 标识该类。

遍历每个为 1 的节点，将它的右边和下边的 1 和当前节点合并（这里算作一个优化，不需要像解法一那样上下左右）。每进行一次合并，我们就将 nums 减 1 。

最后返回 即可。

总

解法一标记的思想前边的题目也遇到过好多次了，解法二的话算作一个通用的解法，当发现题目是分类相关的，可以考虑并查集。

添加好友一起进步~

如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 查看详情