并查集的基本实现和特性
并查集 Disjoint Set。
并查集用来解决组团、配对问题。
基本操作
makeSet(s):建立一个新的并查集,其中包含 s 个单元素集合;
unionSet(x, y):把元素 x 和元素 y 所在的集合合并,要求 x 和 y 所在的集合不相交,如果相交则不合并;
find(x):找到元素 x 所在的集合的代表,该操作也可以用于判断两个元素是否位于同一个集合,只要将它们各自的代表比较一下就可以。
并查集结构
初始化
每一个元素拥有一个 parent 数组指向自己,表示它自己的集合。
查询、合并
查询:对任何一个元素,向上寻找 parent,直到它的 parent 等于它自己,说明找到领头元素,即集合的代表元素。
合并:找出集合的领头元素,讲 parent[e] 指向 a,或者将 parent[a] 指向 e。
路径压缩
关系和原来一致,查询时间会快很多。
代码实现
class UnionFind {
constructor (n) {
this.count = n;
this.parent = new Array(n);
for (let i = 0; i < n; i++) {
this.parent[i] = i;
}
}
find (p) {
let root = p;
while (this.parent[root] != root) {
root = this.parent[root];
}
while (this.parent[p] != p) {
let x = p;
p = this.parent[p];
this.parent[x] = root;
}
return root;
}
union (p, q) {
let rootP = this.find(p);
let rootQ = this.find(q);
if (rootP === rootQ) return;
this.parent[rootP] = rootQ;
this.count--;
}
}
相关题目
朋友圈(亚马逊、Facebook、字节跳动在半年内面试中考过)
岛屿数量(近半年内,亚马逊在面试中考查此题达到 361 次)
被围绕的区域(亚马逊、eBay、谷歌在半年内面试中考过)
// 朋友圈
// 解法1:DFS、BFS 类似岛屿问题
// DFS Java
class Solution {
public int findCircleNum (int[][] M) {
boolean[] visited = new boolen[M.length];
int ret = 0;
// 使用 visited 数组,依次判断每个节点
// 如果未访问,朋友圈数加 1 并对该节点进行 dfs 搜索标记所有访问到的节点
for (int i = 0; i < M.length; i++) {
if (!visted[i]) {
dfs(M, visited, i);
ret++;
}
}
return ret;
}
private void dfs (int[][] m, boolean[] visited, int i) {
for (int j = 0; j < m.length; j++) {
if (m[i][j] == 1 && !visited[j]) {
visited[j] = true;
dfs(m, visited, j);
}
}
}
}
# 朋友圈
# 解法2:并查集
# 并查集 Python
class Solution (object):
def findCricleNum(self, M)
if not M: return 0
n = len(M)
p = [i for i in range(n)]
for i in range(n):
for j in range(n):
if M[i][j] == 1:
self._union(p, i, j)
return len(set[self._parent(p, i) for i in range(n)])
def _union(self, p, i, j):
p1 = self._parent(p, i)
p2 = self._parent(p, j)
p[p2] = p1
def _parent(self, p, i)
root = i
while p[root] != root:
root = p[root]
while p[i] != i:
x = i; i = p[i]; p[x] = root
return root
// 岛屿数量
/**
* 深度优先搜索
* @param {character[][]} grid
* @return {number}
*/
var numIslands = function(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++;
trunZero(i, j, grid);
}
}
}
return count;
};
function trunZero (i, j, grid) {
if (
i < 0 || i >= grid.length ||
j < 0 || j >= grid[0].length || grid[i][j] === '0'
) return;
grid[i][j] = '0';
trunZero(i, j + 1, grid);
trunZero(i, j - 1, grid);
trunZero(i + 1, j, grid);
trunZero(i - 1, j, grid);
}
/**
* 广度优先搜索
* @param {character[][]} grid
* @return {number}
*/
const numIslands = (grid) => {
const queue = [];
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++;
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]);
}
}
}