我的书签
添加书签
移除书签题目描述（中等难度）
一个二维数组，把 1 看做陆地，把 0 看做大海，陆地相连组成一个岛屿。把数组以外的区域也看做是大海，问总共有多少个岛屿。
解法一
想法很简单，我们只需要遍历二维数组，然后遇到 1 的时候，把当前的 1 以及它周围的所有 1 都标记成一个字符，这里直接标记成 2。然后记录遇到了几次 1，就代表有几个岛屿。看下边的例子。
1. [1] 1 0 0 0
2. 1 1 0 0 0
3. 0 0 1 0 0
4. 0 0 0 1 1
5. 当前遇到了 1, count = 1;
6. 把当前的 1 和它周围的 1 标记为 2
7. 2 2 0 0 0
8. 2 2 0 0 0
9. 0 0 1 0 0
10. 0 0 0 1 1
11. 12. 2 2 0 0 0
13. 2 2 0 0 0
14. 0 0 [1] 0 0
15. 0 0 0 1 1
16. 遇到下一个 1, count = 2;
17. 把当前的 1 和它周围的 1 标记为 2
18. 2 2 0 0 0
19. 2 2 0 0 0
20. 0 0 2 0 0
21. 0 0 0 1 1
22. 23. 2 2 0 0 0
24. 2 2 0 0 0
25. 0 0 2 0 0
26. 0 0 0 [1] 1
27. 遇到下一个 1, count = 3;
28. 把当前的 1 和它周围的 1 标记为 2
29. 2 2 0 0 0
30. 2 2 0 0 0
31. 0 0 2 0 0
32. 0 0 0 2 2
33. 34. 没有 1 了，所以岛屿数是 count = 3 个。
还有一个问题就是怎么标记与当前 1 相邻的 1。也很直接，我们直接把和当前 1 连通的位置看做一个图，然后做一个遍历即可。可以直接用递归写一个 DFS，即深度优先遍历。
1. public int numIslands(char[][] grid) {
2. int count = 0;
3. int rows = grid.length;
4. if (rows == 0) {
5. return 0;
6. }
7. int cols = grid[0].length;
8. for (int r = 0; r < rows; r++) {
9. for (int c = 0; c < cols; c++) {
10. if (grid[r][c] == '1') {
11. count++;
12. marked(r, c, rows, cols, grid);
13. }
14. }
15. }
16. return count;
17. }
18. 19. private void marked(int r, int c, int rows, int cols, char[][] grid) {
20. if (r == -1 || c == -1 || r == rows || c == cols || grid[r][c] != '1') {
21. return;
22. }
23. //当前 1 标记为 2
24. grid[r][c] = '2';
25. 26. //向上下左右扩展
27. marked(r + 1, c, rows, cols, grid);
28. marked(r, c + 1, rows, cols, grid);
29. marked(r - 1, c, rows, cols, grid);
30. marked(r, c - 1, rows, cols, grid);
31. 32. }
当然做遍历的话，我们也可以采用 BFS，广度优先遍历。图的广度优先遍历和二叉树的 层次遍历 类似，只需要借助一个队列即可。
和上边的区别不大，改一下标记函数即可。
此外入队列的时候，我们把二维坐标转为了一维，就省去了再创建一个类表示坐标。
1. public int numIslands(char[][] grid) {
2. int count = 0;
3. int rows = grid.length;
4. if (rows == 0) {
5. return 0;
6. }
7. int cols = grid[0].length;
8. for (int r = 0; r < rows; r++) {
9. for (int c = 0; c < cols; c++) {
10. if (grid[r][c] == '1') {
11. count++;
12. bfs(r, c, rows, cols, grid);
13. }
14. }
15. }
16. return count;
17. }
18. private void bfs(int r, int c, int rows, int cols, char[][] grid) {
19. Queue
解法二 并查集
一开始看到这道题，我其实想到的是并查集，然后想了想感觉有些复杂，复杂度可能会高一些，就换了下思路想到了解法一。逛了一下 Discuss 发现也有人用并查集实现了，那这里也再总结下。
并查集在 130 题 中用过一次，把当时的介绍在粘过来。
看下维基百科对 并查集 的定义。
在计算机科学中，并查集 是一种树型的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题。有一个联合-查找算法 （union-find algorithm ）定义了两个用于此数据结构的操作： * Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。 * Union：将两个子集合并成同一个集合。
由于支持这两种操作，一个不相交集也常被称为联合-查找数据结构（union-find data structure）或合并-查找集合（merge-find set）。其他的重要方法，MakeSet，用于创建单元素集合。有了这些方法，许多经典的划分问题可以被解决。 为了更加精确的定义这些方法，需要定义如何表示集合。一种常用的策略是为每个集合选定一个固定的元素，称为代表，以表示整个集合。接着，Find(x) 返回 x 所属集合的代表，而 Union 使用两个集合的代表作为参数。 网上很多讲并查集的文章了，这里推荐 一篇，大家可以先去看一下。 知道了并查集，下边就很好解决了，因为你会发现，我们做的就是分类的问题，把相邻的
1都分成一类。 首先我们把每个节点各作为一类，用它的行数和列数生成一个id标识该类。 1. int node(int i, int j) { 2. return i * cols + j; 3. }
用 nums 来记录当前有多少个岛屿，初始化的时候每个 1 都认为是一个岛屿，然后开始合并。
遍历每个为 1 的节点，将它的右边和下边的 1 和当前节点合并（这里算作一个优化，不需要像解法一那样上下左右）。每进行一次合并，我们就将 nums 减 1 。
最后返回 nums 即可。
1. class UnionFind {
2. int[] parents;
3. int nums;
4. 5. public UnionFind(char[][] grid, int rows, int cols) {
6. nums = 0;
7. // 记录 1 的个数
8. for (int i = 0; i < rows; i++) {
9. for (int j = 0; j < cols; j++) {
10. if (grid[i][j] == '1') {
11. nums++;
12. }
13. }
14. }
15. 16. //每一个类初始化为它本身
17. int totalNodes = rows * cols;
18. parents = new int[totalNodes];
19. for (int i = 0; i < totalNodes; i++) {
20. parents[i] = i;
21. }
22. }
23. 24. void union(int node1, int node2) {
25. int root1 = find(node1);
26. int root2 = find(node2);
27. //发生合并，nums--
28. if (root1 != root2) {
29. parents[root2] = root1;
30. nums--;
31. }
32. }
33. 34. int find(int node) {
35. while (parents[node] != node) {
36. parents[node] = parents[parents[node]];
37. node = parents[node];
38. }
39. return node;
40. }
41. 42. int getNums() {
43. return nums;
44. }
45. }
46. 47. int rows;
48. int cols;
49. 50. public int numIslands(char[][] grid) {
51. if (grid.length == 0)
52. return 0;
53. 54. rows = grid.length;
55. cols = grid[0].length;
56. UnionFind uf = new UnionFind(grid, rows, cols);
57. 58. for (int row = 0; row < rows; row++) {
59. for (int col = 0; col < cols; col++) {
60. if (grid[row][col] == '1') {
61. // 将下边右边的 1 节点和当前节点合并
62. if (row != (rows - 1) && grid[row + 1][col] == '1') {
63. uf.union(node(row, col), node(row + 1, col));
64. }
65. if (col != (cols - 1) && grid[row][col + 1] == '1') {
66. uf.union(node(row, col), node(row, col + 1));
67. }
68. }
69. }
70. }
71. return uf.getNums();
72. 73. }
74. 75. int node(int i, int j) {
76. return i * cols + j;
77. }
总
解法一标记的思想前边的题目也遇到过好多次了，解法二的话算作一个通用的解法，当发现题目是分类相关的，可以考虑并查集。
添加好友一起进步~
如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^
如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情
