# 并查集-查连通区域神器
# 又是被火车撞了都不能忘的东西
1)每个节点都有一条往上指的指针
2)节点a往上找到的头节点,叫做a所在集合的代表节点
3)查询x和y是否属于同一个集合,就是看看找到的代表节点是不是一个
4)把x和y各自所在集合的所有点合并成一个集合,只需要小集合的代表点挂在大集合的代表点的下方即可
# 1.两个核心方法及核心属性
# 核心方法
- boolean isSameSet(a,e) a,e是否属于同一个集合.
- void union(a,e) ,a,e所在的两个集合合并成一个集合.
在调用很频繁,超过样本量的情况,均摊下来,时间复杂度,O(1)
# 核心属性
parent[] :记录当前节点的父亲是谁,用来查代表节点
size[]: size[i] = k,如果i是代表节点,size[i]才有意义,否则无意义,代表的是这个i所在的整个集合的大小是多少
help[] 或者 stack : 用来优化找代表节点,扁平化的过程.
int sets : 用来记录一共有多少个连通区域.
# 2.方法流程示意
# 两个优化点,
小挂大(也是为了第二个优化点)
重要优化!每个节点查找祖先后,==返回前==将沿途所有节点全部直接挂在祖先节点下.==用栈实现==,从哪开始找,只是沿途的链变扁平,那些小箭头,我们不管.目的就是减少链的长度,痛就痛一次.
# 3.证明-别想了
做不到,会用就行了,从1964年提出,1989年才证明出来.
记住了--只要到达样本量的规模,单次就是O(1)
# 4.题目-Leetcode 547 Friend Circles
有
n
个城市,其中一些彼此相连,另一些没有相连。如果城市a
与城市b
直接相连,且城市b
与城市c
直接相连,那么城市a
与城市c
间接相连。省份 是一组直接或间接相连的城市,组内不含其他没有相连的城市。
给你一个
n x n
的矩阵isConnected
,其中isConnected[i][j] = 1
表示第i
个城市和第j
个城市直接相连,而isConnected[i][j] = 0
表示二者不直接相连。返回矩阵中 省份 的数量。
提示:
1 <= n <= 200
n == isConnected.length
n == isConnected[i].length
isConnected[i][j]
为1
或0
isConnected[i][i] == 1
isConnected[i][j] == isConnected[j][i]
https://leetcode.com/problems/friend-circles/
public static int findCircleNum(int[][] M) {
int N = M.length;
// {0} {1} {2} {N-1}
UnionFind unionFind = new UnionFind(N);
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
if (M[i][j] == 1) { // i和j互相认识
unionFind.union(i, j);
}
}
}
return unionFind.sets();
}
public static class UnionFind {
// parent[i] = k : i的父亲是k
private int[] parent;
// size[i] = k : 如果i是代表节点,size[i]才有意义,否则无意义
// i所在的集合大小是多少
private int[] size;
// 辅助结构
private int[] help;
// 一共有多少个集合
private int sets;
public UnionFind(int N) {
parent = new int[N];
size = new int[N];
help = new int[N];
sets = N;
for (int i = 0; i < N; i++) {
parent[i] = i;
size[i] = 1;
}
}
// 从i开始一直往上,往上到不能再往上,代表节点,返回
// 这个过程要做路径压缩
private int find(int i) {
int hi = 0;
while (i != parent[i]) {
help[hi++] = i;
i = parent[i];
}
for (hi--; hi >= 0; hi--) {
parent[help[hi]] = i;
}
return i;
}
public void union(int i, int j) {
int f1 = find(i);
int f2 = find(j);
if (f1 != f2) {
if (size[f1] >= size[f2]) {
size[f1] += size[f2];
parent[f2] = f1;
} else {
size[f2] += size[f1];
parent[f1] = f2;
}
sets--;
}
}
public int sets() {
return sets;
}
}
# 5.岛问题
给定一个二维数组matrix,里面的值不是1就是0, 上、下、左、右相邻的1认为是一片岛, 返回matrix中岛的数量
就是说一个矩阵,不是0就是1,上下左右相邻的1可以连起来,组成一块区域,问,有几个区域.
# 1.感染方法,
# 代码实现
从左往右,从上往下开始遍历,遇到1就感染为2,将上下左右都给改为0,遇到0就跳过,每次遇到1,岛+1,最后返回岛的数量.
public static int numIslands3(char[][] board) {
int islands = 0;
//从左往右
for (int i = 0; i < board.length; i++) {
//从上往下遍历
for (int j = 0; j < board[0].length; j++) {
//遇到1就开始感染过程,否则就跳过,同时岛数量+1
if (board[i][j] == '1') {
islands++;
infect(board, i, j);
}
}
}
return islands;
}
// 从(i,j)这个位置出发,把所有连成一片的'1'字符,变成0
public static void infect(char[][] board, int i, int j) {
if (i < 0 || i == board.length || j < 0 || j == board[0].length || board[i][j] != '1') {
return;
}
board[i][j] = 0;
infect(board, i - 1, j);
infect(board, i + 1, j);
infect(board, i, j - 1);
infect(board, i, j + 1);
}
# 2.并查集方法.
主方法,初始化每个节点,用dot内存地址代表不同的1,
从左往右,上往下,都是1就合并,
public static int numIslands1(char[][] board) {
int row = board.length;
int col = board[0].length;
//我用Dot的内存地址代表1,null代表0
Dot[][] dots = new Dot[row][col];
List<Dot> dotList = new ArrayList<>();
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (board[i][j] == '1') {
dots[i][j] = new Dot();
dotList.add(dots[i][j]);
}
}
}
UnionFind1<Dot> uf = new UnionFind1<>(dotList);
//下面为什么3个for循环,为了省去if,else的判断
//第一个,只处理第一列,他没有左,只看上面
//第二个,只处理第一行,他没有上,只看左边
//第三个,从左往右,从上往下,看左边和上面,省去了判断有没有.
//合并完了后,返回岛数量.
for (int j = 1; j < col; j++) {
// (0,j) (0,0)跳过了 (0,1) (0,2) (0,3)
if (board[0][j - 1] == '1' && board[0][j] == '1') {
uf.union(dots[0][j - 1], dots[0][j]);
}
}
for (int i = 1; i < row; i++) {
if (board[i - 1][0] == '1' && board[i][0] == '1') {
uf.union(dots[i - 1][0], dots[i][0]);
}
}
for (int i = 1; i < row; i++) {
for (int j = 1; j < col; j++) {
if (board[i][j] == '1') {
if (board[i][j - 1] == '1') {
uf.union(dots[i][j - 1], dots[i][j]);
}
if (board[i - 1][j] == '1') {
uf.union(dots[i - 1][j], dots[i][j]);
}
}
}
}
return uf.sets();
}
//里面是空的无所有,我用null代表0,非null的地址表示1
public static class Dot {
}
public static class Node<V> {
V value;
public Node(V v) {
value = v;
}
}
//HashMap实现,已经是时间复杂度最优解,但是常数时间大
public static class UnionFind1<V> {
public HashMap<V, Node<V>> nodes;
public HashMap<Node<V>, Node<V>> parents;
public HashMap<Node<V>, Integer> sizeMap;
public UnionFind1(List<V> values) {
nodes = new HashMap<>();
parents = new HashMap<>();
sizeMap = new HashMap<>();
for (V cur : values) {
Node<V> node = new Node<>(cur);
nodes.put(cur, node);
parents.put(node, node);
sizeMap.put(node, 1);
}
}
//优化过程,扁平化
public Node<V> findFather(Node<V> cur) {
Stack<Node<V>> path = new Stack<>();
while (cur != parents.get(cur)) {
path.push(cur);
cur = parents.get(cur);
}
while (!path.isEmpty()) {
parents.put(path.pop(), cur);
}
return cur;
}
public void union(V a, V b) {
Node<V> aHead = findFather(nodes.get(a));
Node<V> bHead = findFather(nodes.get(b));
if (aHead != bHead) {
int aSetSize = sizeMap.get(aHead);
int bSetSize = sizeMap.get(bHead);
Node<V> big = aSetSize >= bSetSize ? aHead : bHead;
Node<V> small = big == aHead ? bHead : aHead;
parents.put(small, big);
sizeMap.put(big, aSetSize + bSetSize);
sizeMap.remove(small);
}
}
public int sets() {
return sizeMap.size();
}
}
# 3.并查集的优化
用数组来减少常数时间
public static int numIslands2(char[][] board) {
int row = board.length;
int col = board[0].length;
UnionFind2 uf = new UnionFind2(board);
for (int j = 1; j < col; j++) {
if (board[0][j - 1] == '1' && board[0][j] == '1') {
uf.union(0, j - 1, 0, j);
}
}
for (int i = 1; i < row; i++) {
if (board[i - 1][0] == '1' && board[i][0] == '1') {
uf.union(i - 1, 0, i, 0);
}
}
for (int i = 1; i < row; i++) {
for (int j = 1; j < col; j++) {
if (board[i][j] == '1') {
if (board[i][j - 1] == '1') {
uf.union(i, j - 1, i, j);
}
if (board[i - 1][j] == '1') {
uf.union(i - 1, j, i, j);
}
}
}
}
return uf.sets();
}
public static class UnionFind2 {
private int[] parent;
private int[] size;
private int[] help;
private int col;
private int sets;
public UnionFind2(char[][] board) {
col = board[0].length;
sets = 0;
int row = board.length;
int len = row * col;
parent = new int[len];
size = new int[len];
help = new int[len];
for (int r = 0; r < row; r++) {
for (int c = 0; c < col; c++) {
if (board[r][c] == '1') {
int i = index(r, c);
parent[i] = i;
size[i] = 1;
sets++;
}
}
}
}
// (r,c) -> i
private int index(int r, int c) {
return r * col + c;
}
// 原始位置 -> 下标
private int find(int i) {
int hi = 0;
while (i != parent[i]) {
help[hi++] = i;
i = parent[i];
}
for (hi--; hi >= 0; hi--) {
parent[help[hi]] = i;
}
return i;
}
public void union(int r1, int c1, int r2, int c2) {
int i1 = index(r1, c1);
int i2 = index(r2, c2);
int f1 = find(i1);
int f2 = find(i2);
if (f1 != f2) {
if (size[f1] >= size[f2]) {
size[f1] += size[f2];
parent[f2] = f1;
} else {
size[f2] += size[f1];
parent[f1] = f2;
}
sets--;
}
}
public int sets() {
return sets;
}
}
# 6.岛问题扩展 leetcode 305
一开始没有点为1,而是一个个空降来的,要求返回每次空降完1后的岛数量.
# 代码
public static List<Integer> numIslands21(int m, int n, int[][] positions) {
//初始化并查集结构
UnionFind1 uf = new UnionFind1(m, n);
//答案集合,等收集并且返回用.
List<Integer> ans = new ArrayList<>();
for (int[] position : positions) {
ans.add(uf.connect(position[0], position[1]));
}
return ans;
}
//同样的一维数组表示二维,为了快,
public static class UnionFind1 {
private int[] parent;
private int[] size;
private int[] help;
private final int row;
private final int col;
private int sets;
public UnionFind1(int m, int n) {
row = m;
col = n;
sets = 0;
int len = row * col;
parent = new int[len];
size = new int[len];
help = new int[len];
}
//计算二维中的位置在一维数组中的哪里
private int index(int r, int c) {
return r * col + c;
}
//查找代表节点,同样是有优化的,扁平化处理.
private int find(int i) {
int hi = 0;
while (i != parent[i]) {
help[hi++] = i;
i = parent[i];
}
for (hi--; hi >= 0; hi--) {
parent[help[hi]] = i;
}
return i;
}
//合并.不越界,都是1,不是一个代表节点,就可以合并,
private void union(int r1, int c1, int r2, int c2) {
if (r1 < 0 || r1 == row || r2 < 0 || r2 == row || c1 < 0 || c1 == col || c2 < 0 || c2 == col) {
return;
}
int i1 = index(r1, c1);
int i2 = index(r2, c2);
if (size[i1] == 0 || size[i2] == 0) {
return;
}
int f1 = find(i1);
int f2 = find(i2);
if (f1 != f2) {
if (size[f1] >= size[f2]) {
size[f1] += size[f2];
parent[f2] = f1;
} else {
size[f2] += size[f1];
parent[f1] = f2;
}
sets--;
}
}
//之前没有将size还原,是为了判断是否空降过,初始化过.
public int connect(int r, int c) {
int index = index(r, c);
if (size[index] == 0) {
parent[index] = index;
size[index] = 1;
sets++;
union(r - 1, c, r, c);
union(r + 1, c, r, c);
union(r, c - 1, r, c);
union(r, c + 1, r, c);
}
return sets;
}
}
# 复杂度分析
初始化O(m*n)
,k个点就是O(k),最慢的瓶颈还是那个O(m*n)
如果mn极大,而空降的位置k不大,
那我就不急着初始化表了,空降一个再去找上下左右去感染
# 数据极大的情况下,优化方法
public static List<Integer> numIslands22(int m, int n, int[][] positions) {
UnionFind2 uf = new UnionFind2();
List<Integer> ans = new ArrayList<>();
for (int[] position : positions) {
ans.add(uf.connect(position[0], position[1]));
}
return ans;
}
public static class UnionFind2 {
private HashMap<String, String> parent;
private HashMap<String, Integer> size;
private ArrayList<String> help;
private int sets;
public UnionFind2() {
parent = new HashMap<>();
size = new HashMap<>();
help = new ArrayList<>();
sets = 0;
}
private String find(String cur) {
while (!cur.equals(parent.get(cur))) {
help.add(cur);
cur = parent.get(cur);
}
for (String str : help) {
parent.put(str, cur);
}
help.clear();
return cur;
}
private void union(String s1, String s2) {
if (parent.containsKey(s1) && parent.containsKey(s2)) {
String f1 = find(s1);
String f2 = find(s2);
if (!f1.equals(f2)) {
int size1 = size.get(f1);
int size2 = size.get(f2);
String big = size1 >= size2 ? f1 : f2;
String small = big == f1 ? f2 : f1;
parent.put(small, big);
size.put(big, size1 + size2);
sets--;
}
}
}
public int connect(int r, int c) {
String key = String.valueOf(r) + "_" + String.valueOf(c);
if (!parent.containsKey(key)) {
parent.put(key, key);
size.put(key, 1);
sets++;
String up = String.valueOf(r - 1) + "_" + String.valueOf(c);
String down = String.valueOf(r + 1) + "_" + String.valueOf(c);
String left = String.valueOf(r) + "_" + String.valueOf(c - 1);
String right = String.valueOf(r) + "_" + String.valueOf(c + 1);
union(up, key);
union(down, key);
union(left, key);
union(right, key);
}
return sets;
}
}
# 7.回到普通的岛问题,一开始就给你所有的0和1,设计并行计算方案
- 随便切,切完了每块该怎么算,怎么算,算出每块多少个岛
- 算出边界的那个位置的是由谁感染或者连起来的.
- 将边界拿掉,边界两侧的,如果值一样,需要合并,代表的是他们背后所有的东西合并到一起,岛--.
- 每个区域来4个边,收集4条边的信息,最后,开始合并
- 都没有现场冲突问题,不需要加锁,合并就完事了.