大厂算法面试之leetcode精讲23.并查集
视频讲解（高效学习）:点击学习
目录：
并查集（union & find）：用于处理一些元素的合并和查询问题
Find：确定元素属于哪一个子集，他可以被用来确定两个元素是否属于同一个子集，加入路径压缩，复杂度近乎O(1)
Union：将两个子集合并成同一个集合
// 0,1,2,3
//parent: 0,1,2,3
//size: 1,1,1,1
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;
}
}
// 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];
}
}