并查集

评论

并查集

并查集一种数据结构，可以用一个 Class 来实现。可以把一组数据关联起来，然后统计数量。
可以用来解决岛屿数量的问题。

实现

  • 使用一个数组来保存每一项的父节点
  • 使用一个数组来保存每一项的层级
  • 一个 findRoot 方法，可以找到一项的根
  • 一个 union 方法，如果两项的根不同，可以合并两项的根，使他们俩的根相同
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class UnionFind {
  parent: number[] = [];
  rank: number[] = [];
  count: number = 0;
  constructor(nums: number[][]) {
    const m = nums.length;
    const n = nums[0].length;

    for (let i = 0; i < m; i++) {
      for (let j = 0; j < n; j++) {
        this.rank[i * n + j] = 0;
        if (nums[i][j]) {
          this.parent[i * n + j] = i * n + j;
          this.count++;
        }
      }
    }
  }

  find(num: number): number {
    if (this.parent[num] !== num) {
      this.parent[num] = this.find(this.parent[num]);
    }
    return this.parent[num];
  }

  union(x: number, y: number) {
    const rootX = this.find(x);
    const rootY = this.find(y);

    if (rootX !== rootY) {
      if (this.rank[rootX] < this.rank[rootY]) {
        this.parent[rootX] = rootY;
      } else if (this.rank[rootX] > this.rank[rootY]) {
        this.parent[rootY] = rootX;
      } else {
        // rank rootX 等于 rank rootY
        this.parent[rootX] = rootY;
        this.rank[rootY]++;
      }
      this.count--;
    }
  }
}