leetcode地址：200. 島嶼數量

解答參考：島嶼數量官方解答

問題描述：

給你一個由?'1'（陸地）和 '0'（水）組成的的二維網格，請你計算網格中島嶼的數量。島嶼總是被水包圍，并且每座島嶼只能由水平方向和/或豎直方向上相鄰的陸地連接形成。此外，你可以假設該網格的四條邊均被水包圍。示例 1：

輸入：grid = [

? ["1","1","1","1","0"],

? ["1","1","0","1","0"],

? ["1","1","0","0","0"],

? ["0","0","0","0","0"]

]

輸出：1

算法思路：

本題可以采用深度優先搜索、廣度優先搜索、并查集三種方式求解，本篇文章講解使用并查集的方法

class Solution {class UnionFind {//根節點數量int count;//保存每個節點的根節點是誰的集合int[] parent;//保存每個節點的下級節點的數量int[] rank;/**假設grid為* [["1","1","1","1","0"],* ["1","1","0","1","0"],* ["1","1","0","0","0"],* ["0","0","0","0","0"]]* 初始化的parent* [0,1,2,3,0,* 5,6,0,8,0,* 10,11,0,0,0,* 0,0,0,0,0]*初始化的rank = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]*/public UnionFind(char[][] grid) {count = 0;int m = grid.length;int n = grid[0].length;parent = new int[m * n];rank = new int[m * n];for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (grid[i][j] == '1') {//每個節點的根節點為自己（下標與值相等）parent[i * n + j] = i * n + j;++count;}rank[i * n + j] = 0;}}}public int find(int i) {//如果下標與值不相等，則遞歸尋找根節點if (parent[i] != i) parent[i] = find(parent[i]);return parent[i];}public void union(int x, int y) {//找到x、y的根節點int rootx = find(x);int rooty = find(y);//如果根節點不同進行合并if (rootx != rooty) {if (rank[rootx] > rank[rooty]) {parent[rooty] = rootx;} else if (rank[rootx] < rank[rooty]) {parent[rootx] = rooty;} else {parent[rooty] = rootx;rank[rootx] += 1;}//合并一個節點就減少一個節點--count;}}public int getCount() {return count;}}public int numIslands(char[][] grid) {if (grid == null || grid.length == 0) {return 0;}int nr = grid.length;int nc = grid[0].length;int num_islands = 0;UnionFind uf = new UnionFind(grid);for (int r = 0; r < nr; r++) {for (int c = 0; c < nc; c++) {if (grid[r][c] == '1') {grid[r][c] = '0';//當前節點的上方節點與當前節點進行合并if (r - 1 >= 0 && grid[r-1][c] == '1') {uf.union(r * nc + c, (r-1) * nc + c);}//當前節點的下方節點與當前節點進行合并if (r + 1 < nr && grid[r+1][c] == '1') {uf.union(r * nc + c, (r+1) * nc + c);}//當前節點的左方節點與當前節點進行合并if (c - 1 >= 0 && grid[r][c-1] == '1') {uf.union(r * nc + c, r * nc + c - 1);}//當前節點的右方節點與當前節點進行合并if (c + 1 < nc && grid[r][c+1] == '1') {uf.union(r * nc + c, r * nc + c + 1);}}}}return uf.getCount();} }

?復雜度分析

時間復雜度：O(MN?α(MN))，其中 MM 和 NN 分別為行數和列數。注意當使用路徑壓縮（見 find 函數）和按秩合并（見數組 rank）實現并查集時，單次操作的時間復雜度為 α(MN)，其中α(x) 為反阿克曼函數，當自變量 x 的值在人類可觀測的范圍內（宇宙中粒子的數量）時，函數 α(x) 的值不會超過 55，因此也可以看成是常數時間復雜度。

空間復雜度：O(MN)，這是并查集需要使用的空間。

超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的并查集—岛屿数量的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。