大厂算法面试之 leetcode 精讲 23. 并查集
作者：全栈潇晨
- 2021 年 12 月 07 日
本文字数：9228 字
阅读完需：约 30 分钟
大厂算法面试之 leetcode 精讲 23.并查集
视频讲解（高效学习）:点击学习
目录：
并查集（union & find）：用于处理一些元素的合并和查询问题
Find：确定元素属于哪一个子集，他可以被用来确定两个元素是否属于同一个子集，加入路径压缩，复杂度近乎O(1)
Union：将两个子集合并成同一个集合
// 0,1,2,3//parent: 0,1,2,3//size: 1,1,1,1class UnionFind{ constructor(n){ //构造一个大小为n的集合 this.count = n this.parent = new Array(n) this.size = new Array(n) // size数组记录着每棵树的大小 for (let i = 0; i < n; i++) { this.parent[i] = i; // 自己是自己的parent this.size[i] = 1; } }
union(p,q){ //连通结点p和结点q, p和q都是索引 let rootP = this.find(p); let rootQ = this.find(q); if(rootP === rootQ) return // 元素数量小的接到数量多的下面，这样比较平衡 if (this.size[rootP] > this.size[rootQ]) { this.parent[rootQ] = rootP; this.size[rootP] += this.size[rootQ]; } else { this.parent[rootP] = rootQ; this.size[rootQ] += this.size[rootP]; } this.count--; }
isConnected(p, q) { //判断p,q是否连通 return this.find(p)=== this.find(q) }
find(x) { //找到x结点的root while (this.parent[x] != x) { // 进行路径压缩 this.parent[x] = this.parent[this.parent[x]]; x = this.parent[x]; } return x; }
getCount() { //返回子集个数 return this.count; }}
// 0,1,2,3//parent: 0,1,2,3//rank: 1,1,1,1//采用rank优化class UnionFind { constructor(n) { //构造一个节点数为n的集合 this.count = n //并查集总数 this.parent = new Array(n) this.rank = new Array(n) // rank数组记录着每棵树的重量 for (let i = 0; i < n; i++) { this.parent[i] = i; // 自己是自己的parent this.rank[i] = 1; //每个集合上节点的数量 } }
union(p, q) { //连通结点p和结点q, p和q都是索引 let rootP = this.find(p); let rootQ = this.find(q); if (rootP === rootQ) return // 深度小的接在深度大元素下 if (this.rank[rootP] > this.rank[rootQ]) { this.parent[rootQ] = rootP; } else if (this.rank[rootP] < this.rank[rootQ]) { this.parent[rootP] = rootQ; } else { this.parent[rootP] = rootQ; this.rank[rootQ]++ } this.count--; }
isConnected(p, q) { //判断p,q是否连通 return this.find(p) === this.find(q) }
find(x) { //找到x结点的root while (this.parent[x] != x) { // 进行路径压缩 this.parent[x] = this.parent[this.parent[x]]; x = this.parent[x]; } return x; }
getCount() { //返回子集个数 return this.count; }}
复制代码
200. 岛屿数量 (medium)
方法 1.dfs
思路：循环网格，深度优先遍历每个坐标的四周，注意坐标不要越界，遇到陆地加 1，并沉没四周的陆地，这样就不会重复计算
复杂度：时间复杂度
O(mn), m 和 n 是行数和列数。空间复杂度是O(mn),最坏的情况下所有网格都需要递归，递归栈深度达到m * n
js：
const numIslands = (grid) => { let count = 0 for (let i = 0; i < grid.length; i++) { for (let j = 0; j < grid[0].length; j++) {//循环网格 if (grid[i][j] === '1') {//如果为陆地，count++， count++ turnZero(i, j, grid) } } } return count}function turnZero(i, j, grid) {//沉没四周的陆地 if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] === '0') return //检查坐标的合法性 grid[i][j] = '0'//让四周的陆地变为海水 turnZero(i, j + 1, grid) turnZero(i, j - 1, grid) turnZero(i + 1, j, grid) turnZero(i - 1, j, grid)}
复制代码
java：
class Solution { void dfs(char[][] grid, int r, int c) { int nr = grid.length; int nc = grid[0].length;
if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') { return; }
grid[r][c] = '0'; dfs(grid, r - 1, c); dfs(grid, r + 1, c); dfs(grid, r, c - 1); dfs(grid, r, c + 1); }
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; for (int r = 0; r < nr; ++r) { for (int c = 0; c < nc; ++c) { if (grid[r][c] == '1') { ++num_islands; dfs(grid, r, c); } } }
return num_islands; }}
复制代码
方法 2.bfs
思路：循环网格，广度优先遍历坐标的四周，遇到陆地加 1，沉没四周的陆地，不重复计算陆地数
复杂度：时间复杂度
O(mn),m 和 n 是行数和列数。空间复杂度是O(min(m，n)),队列的长度最坏的情况下需要能容得下 m 和 n 中的较小者
js:
const numIslands = (grid) => { let count = 0 let queue = [] for (let i = 0; i < grid.length; i++) { for (let j = 0; j < grid[0].length; j++) { if (grid[i][j] === '1') { count++ grid[i][j] = '0' // 做标记，避免重复遍历 queue.push([i, j]) //加入队列 turnZero(queue, grid) } } } return count}function turnZero(queue, grid) { const dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]] while (queue.length) {//当队列中还有元素的时候 const cur = queue.shift() //取出队首元素 for (const dir of dirs) {//四个方向广度优先扩散 const x = cur[0] + dir[0] const y = cur[1] + dir[1] if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] !== '1') { continue }//检查坐标合法性 grid[x][y] = '0' //沉没陆地 queue.push([x, y]) //四周的节点加入队列 } }}
复制代码
java:
class Solution { 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;
for (int r = 0; r < nr; ++r) { for (int c = 0; c < nc; ++c) { if (grid[r][c] == '1') { ++num_islands; grid[r][c] = '0'; Queue<Integer> neighbors = new LinkedList<>(); neighbors.add(r * nc + c); while (!neighbors.isEmpty()) { int id = neighbors.remove(); int row = id / nc; int col = id % nc; if (row - 1 >= 0 && grid[row-1][col] == '1') { neighbors.add((row-1) * nc + col); grid[row-1][col] = '0'; } if (row + 1 < nr && grid[row+1][col] == '1') { neighbors.add((row+1) * nc + col); grid[row+1][col] = '0'; } if (col - 1 >= 0 && grid[row][col-1] == '1') { neighbors.add(row * nc + col-1); grid[row][col-1] = '0'; } if (col + 1 < nc && grid[row][col+1] == '1') { neighbors.add(row * nc + col+1); grid[row][col+1] = '0'; } } } } }
return num_islands; }}
复制代码
方法 3.并查集
思路：
复杂度：时间复杂度
O(mn)，时间复杂度其实是O(mn * f(mn))，f 是采用并查集路径压缩时的复杂度，为常数，所以可以忽略。 m 和 n 是行数和列数。空间复杂度是O(mn),并查集的空间
js:
class UnionFind { constructor(n) { //构造一个节点数为n的集合 this.count = n //并查集总数 this.parent = new Array(n) this.size = new Array(n) // size数组记录着每棵树的重量 for (let i = 0; i < n; i++) { this.parent[i] = i; // 自己是自己的parent this.size[i] = 1; //每个集合上节点的数量 } }
union(p, q) { //连通结点p和结点q, p和q都是索引 let rootP = this.find(p); let rootQ = this.find(q); if (rootP === rootQ) return // 元素数量小的接到数量多的下面，这样比较平衡 if (this.size[rootP] > this.size[rootQ]) { this.parent[rootQ] = rootP; this.size[rootP] += this.size[rootQ]; } else { this.parent[rootP] = rootQ; this.size[rootQ] += this.size[rootP]; } this.count--; }
isConnected(p, q) { //判断p,q是否连通 return this.find(p) === this.find(q) }
find(x) { //找到x结点的root while (this.parent[x] != x) { // 进行路径压缩 this.parent[x] = this.parent[this.parent[x]]; x = this.parent[x]; } return x; }
getCount() { //返回子集个数 return this.count; }
}
var numIslands = function (grid) { let m = grid.length if (m === 0) return 0 let n = grid[0].length const dummy = -1 const dirs = [[1, 0], [0, 1]]//方向数组 向右 向下 const uf = new UnionFind(m * n) for (let x = 0; x < m; x++) { for (let y = 0; y < n; y++) if (grid[x][y] === '0') {//如果网格是0，则和dummy合并 uf.union(n * x + y, dummy) } else if (grid[x][y] === '1') {//如果网格是1，则向右 向下尝试 for (let d of dirs) { let r = x + d[0] let c = y + d[1] if (r >= m || c >= n) continue //坐标合法性 if (grid[r][c] === '1') { //当前网格的右边 下面如果是1，则和当前网格合并 uf.union(n * x + y, n * r + c) } } } } return uf.getCount() //返回并查集的个数减一就行};
复制代码
Java:
class Solution { class UnionFind { int count; int[] parent; int[] rank;
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) { 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(); }}
复制代码
547. 省份数量(medium)
方法 1.dfs
思路：深度优先遍历，visited 记录是否访问过，循环省份数组，递归寻找 isConnected 矩阵中相邻的城市。
复杂度：时间复杂度
O(n^2)，n 是城市的数量，遍历矩阵中的每个元素。空间复杂度O(n)，递归深度不超过 n
js
var findCircleNum = function(isConnected) { const rows = isConnected.length; const visited = new Set();//记录是否访问过 let count = 0;//省份数量 for (let i = 0; i < rows; i++) { if (!visited.has(i)) {//如果没访问过 dfs(isConnected, visited, rows, i);//深度优先遍历 count++;//省份数量+1 } } return count;};
const dfs = (isConnected, visited, rows, i) => { for (let j = 0; j < rows; j++) { if (isConnected[i][j] == 1 && !visited.has(j)) {//如果i，j相连接 visited.add(j); dfs(isConnected, visited, rows, j);//递归遍历 } }};
复制代码
java:
class Solution { public int findCircleNum(int[][] isConnected) { int rows = isConnected.length; boolean[] visited = new boolean[rows]; int count = 0; for (int i = 0; i < rows; i++) { if (!visited[i]) { dfs(isConnected, visited, rows, i); count++; } } return count; }
public void dfs(int[][] isConnected, boolean[] visited, int rows, int i) { for (int j = 0; j < rows; j++) { if (isConnected[i][j] == 1 && !visited[j]) { visited[j] = true; dfs(isConnected, visited, rows, j); } } }}
复制代码
方法 2.bfs
思路：广度优先遍历，循矩阵，然后寻找相邻城市加入队列，队列不为空就不断出队，继续遍历
复杂度：时间复杂度
O(n^2)，n 是城市的数量，遍历矩阵中的每个元素。空间复杂度O(n)，队列和 visited 数组最长是 n
js:
var findCircleNum = function(isConnected) { const rows = isConnected.length; const visited = new Set();//记录是否访问过 let count = 0; const queue = new Array(); for (let i = 0; i < rows; i++) { if (!visited.has(i)) {//没有访问过 queue.push(i); //加入队列 while (queue.length) {//队列不为空 继续循环 const j = queue.shift();//出队 visited.add(j); for (let k = 0; k < rows; k++) {//循环相邻的城市 加入队列 if (isConnected[j][k] === 1 && !visited.has(k)) { queue.push(k); } } } count++; } } return count;};
复制代码
Java:
class Solution { public int findCircleNum(int[][] isConnected) { int rows = isConnected.length; boolean[] visited = new boolean[rows]; int count = 0; Queue<Integer> queue = new LinkedList<Integer>(); for (int i = 0; i < rows; i++) { if (!visited[i]) { queue.offer(i); while (!queue.isEmpty()) { int j = queue.poll(); visited[j] = true; for (int k = 0; k < rows; k++) { if (isConnected[j][k] == 1 && !visited[k]) { queue.offer(k); } } } count++; } } return count; }}
复制代码
方法 3.并查集
思路：循环矩阵，遇到相邻的城市就合并，最后返回并查集中集合的数量
复杂度：时间复杂度
O(n^2)，n 是城市的数量，需要遍历矩阵，经过路径压缩后的并查集中需找父节点复杂度是常数级。空间复杂度是O(n)，即 parent 的空间
js:
class UnionFind{ constructor(n){ //构造一个大小为n的集合 this.count = n this.parent = new Array(n) this.size = new Array(n) // size数组记录着每棵树的大小 for (let i = 0; i < n; i++) { this.parent[i] = i; // 自己是自己的parent this.size[i] = 1; } }
union(p,q){ //连通结点p和结点q, p和q都是索引 let rootP = this.find(p); let rootQ = this.find(q); if(rootP === rootQ) return // 元素数量小的接到数量多的下面，这样比较平衡 if (this.size[rootP] > this.size[rootQ]) { this.parent[rootQ] = rootP; this.size[rootP] += this.size[rootQ]; } else { this.parent[rootP] = rootQ; this.size[rootQ] += this.size[rootP]; } this.count--; }
isConnected(p, q) { //判断p,q是否连通 return this.find(p)=== this.find(q) }
find(x) { //找到x结点的root while (this.parent[x] != x) { // 进行路径压缩 this.parent[x] = this.parent[this.parent[x]]; x = this.parent[x]; } return x; }
getCount() { //返回子集个数 return this.count; }}
var findCircleNum = function(isConnected) { const rows = isConnected.length; const uf = new UnionFind(rows)
for (let i = 0; i < rows; i++) { for (let j = i + 1; j < rows; j++) { if (isConnected[i][j] == 1) {//相邻城市合并 uf.union(i, j); } } }
return uf.getCount();};
复制代码
Java:
class Solution { public int findCircleNum(int[][] isConnected) { int rows = isConnected.length; int[] parent = new int[rows]; for (int i = 0; i < rows; i++) { parent[i] = i; } for (int i = 0; i < rows; i++) { for (int j = i + 1; j < rows; j++) { if (isConnected[i][j] == 1) { union(parent, i, j); } } } int count = 0; for (int i = 0; i < rows; i++) { if (parent[i] == i) { count++; } } return count; }
public void union(int[] parent, int index1, int index2) { parent[find(parent, index1)] = find(parent, index2); }
public int find(int[] parent, int index) { if (parent[index] != index) { parent[index] = find(parent, parent[index]); } return parent[index]; }}
复制代码
划线
评论
复制
发布于: 2 小时前阅读数: 4
全栈潇晨
关注
还未添加个人签名 2021.02.17 加入
还未添加个人简介
评论