前言: 最近发现了一个很有趣的算法,那就是并查集,如果你不了解什么是并查集的话,我希望你能看看下面的文章,因为它真的是一个十分有趣且有用的算法结构!
情景引入:
假设有 a、b、c、d、e、f 六个样本,首先设这几个小样本在自己的集合里 {a}、{b}、{c}、{d}、{e}、{f},针对上述介绍有以下两个操作
boolean isSameSet(a, e)
: 查询 a 和 e 两个样本是否在一个集合void union(a, e)
: 将 a 所在的集合的全体和 e 所在的集合的全体变成一个集合而使用并查集的作用就是,假设有 N 个这样的样本,如果频繁使用上述两个操作能够均摊下来后让时间复杂度为 O(1)
并查集的做法:
下面用并查集的方式,实现了上述情景的两种操作,并且保证了均摊的时间复杂度为 O(1)。可以通过数组代替 HashMap 来提高效率,因为 HashMap 中的常数是大常数
import java.util.HashMap;
import java.util.List;
import java.util.Stack;
// 并查集的实现
public class UnionFind<V> {
// 节点
public static class Node<V> {
V value;
public Node(V value) {
this.value = value;
}
}
// 用来存储每个集合的样本和节点
public HashMap<V, Node<V>> nodes;
// 用来存储子节点和父节点的对应关系(前子后父)
public HashMap<Node<V>, Node<V>> parents;
// 用来存储每个样本所在的集合的样本个数
public HashMap<Node<V>, Integer> sizeMap;
// 初始化并查集(values 表示样本值)
public UnionFind(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.add(cur);
cur = parents.get(cur);
}
while (!path.isEmpty()) {
parents.put(path.pop(), cur);
}
return cur;
}
// 判断 a 和 b 样本是否在一个集合中
public boolean isSameSet(V a, V b) {
return findFather(nodes.get(a)) == findFather(nodes.get(b));
}
// 将 a 和 b 样本所在的集合合并
public void union(V a, V b) {
// 得到 a 和 b 样本的代表节点
Node<V> aHead = findFather(nodes.get(a));
Node<V> bHead = findFather(nodes.get(b));
if (aHead != bHead) {
// 得到这两个集合的样本个数
int aSize = sizeMap.get(aHead);
int bSize = sizeMap.get(bHead);
// 将得到的代表节点进行重定向
// max 表示样本个数多的代表节点
// min 表示样本个数少的代表节点
Node<V> big = aSize > bSize ? aHead : bHead;
Node<V> small = big == aHead ? bHead : aHead;
parents.put(small, big);
sizeMap.put(big, aSize + bSize);
sizeMap.remove(small);
}
}
}
方法: 本题运用并查集的思想,但与上述模板不同,这里将上述模板的 Map 改用数组实现,用数组实现其实效率会更高!
public static int findCircleNum(int[][] isConnected) {
int N = isConnected.length;
UnionFind unionFind = new UnionFind(N);
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
if (isConnected[i][j] == 1) {
unionFind.union(i, j);
}
}
}
return unionFind.sets();
}
public static class UnionFind {
// 表示父子节点关系 parents[i]=k i为子节点,k为父节点
public int[] parents;
// 表示含有当前节点的集合所有的节点数
public int[] size;
// 辅助节点,用于在压缩路径时充当栈
public int[] help;
// 集合的个数
public int sets;
public UnionFind(int N) {
parents = new int[N];
size = new int[N];
help = new int[N];
sets = N;
for (int i = 0; i < N; i++) {
parents[i] = i;
size[i] = 1;
}
}
public int findFather(int cur) {
int count = 0;
while (cur != parents[cur]) {
help[count++] = cur;
cur = parents[cur];
}
for (int i = 0; i < count; i++) {
parents[help[i]] = cur;
}
return cur;
}
public void union(int a, int b) {
int aHead = findFather(a);
int bHead = findFather(b);
if (aHead != bHead) {
int aSize = size[aHead];
int bSize = size[bHead];
int big = (aSize >= bSize) ? aHead : bHead;
int small = (big == aHead) ? bHead : aHead;
size[big] += size[small];
parents[small] = big;
sets--;
}
}
public int sets() {
return sets;
}
}
力扣链接:省份数量
方法一(递归): 可以从左往右从上往下依次遍历,如果该位置的值为0或2,我们就跳过;如果为1,则将该位置上下左右值为1的位置的值变成2,岛的数量加1,依次遍历完整个数组。重点点就是实现这个 inflect 感染方法来更改数组值为1位置的值
public static int numIslands(char[][] grid) {
int islands = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == '1') {
islands++;
infect(grid, i, j);
}
}
}
return islands;
}
public static void infect(char[][] grip, int i, int j) {
if (i < 0 || i == grip.length || j < 0 || j == grip[0].length || grip[i][j] != '1') {
return;
}
grip[i][j] = '2';
infect(grip, i - 1, j);
infect(grip, i + 1, j);
infect(grip, i, j - 1);
infect(grip, i, j + 1);
}
方法二(并查集): 可以使用并查集的方法,我们只需要对每个数组位置进行左和上的 union,就可以求得岛的数量
public static int numIslands2(char[][] grid) {
UnionFind unionFind = new UnionFind(grid);
// 对第一行遍历(用来为后面遍历排除边界条件,注意 0 0 位置不需要遍历,因为它没有左和上的位置)
for(int i=1;i<grid[0].length;i++) {
if(grid[0][i]=='1'&&grid[0][i-1]=='1') {
unionFind.union(unionFind.index(0, i), unionFind.index(0, i-1));
}
}
// 对第一列遍历(用来为后面遍历排除边界条件,注意 0 0 位置不需要遍历,因为它没有左和上的位置)
for(int i=1;i<grid.length;i++) {
if(grid[i][0]=='1'&&grid[i-1][0]=='1') {
unionFind.union(unionFind.index(i, 0), unionFind.index(i-1, 0));
}
}
// 对右下角遍历
for(int i=1;i<grid.length;i++) {
for(int j=1;j<grid[0].length;j++) {
if(grid[i][j]=='1'&&grid[i][j-1]=='1') {
unionFind.union(unionFind.index(i, j), unionFind.index(i, j-1));
}
if((grid[i][j]=='1'&&grid[i-1][j]=='1')) {
unionFind.union(unionFind.index(i, j), unionFind.index(i-1, j));
}
}
}
return unionFind.sets();
}
public static class UnionFind{
// 子节点的父节点
public int[] parents;
// 含有该节点的集合的节点数
public int[] size;
// 辅助节点
public int[] help;
// 集合个数
public int sets;
// 数组列数
public int col;
public UnionFind(char[][] grid) {
col = grid[0].length;
int N = col*grid.length;
parents=new int[N];
size=new int[N];
help=new int[N];
sets=0;
for(int i=0;i<grid.length;i++) {
for(int j=0;j<col;j++) {
if(grid[i][j]=='1') {
int index=index(i,j);
parents[index]=index;
size[index]=1;
sets++;
}
}
}
}
public int findFather(int cur) {
int count=0;
while(cur!=parents[cur]) {
help[count++]=cur;
cur=parents[cur];
}
for(int i=0;i<count;i++) {
parents[help[i]]=cur;
}
return cur;
}
public int index(int i,int j) {
return i*col+j;
}
public void union(int i,int j) {
int iHead=findFather(i);
int jHead=findFather(j);
if(iHead!=jHead) {
int iSize=size[i];
int jSize=size[j];
int big= iSize>jSize?iHead:jHead;
int small=big==iHead?jHead:iHead;
parents[small]=big;
size[big]+=size[small];
sets--;
}
}
public int sets() {
return sets;
}
}
力扣链接:岛屿数量I
方法: 该题使用并查集,与题二不同的是,这题是将陆地给新增,然后求得新增岛屿的数量,岛屿的数量不是固定的。这里的做法和题二相仿,只不过增加了个动态的将新增的陆地进行岛屿数量确定的方法
public static List<Integer> numIslands(int m, int n, int[][] positions) {
UnionFind unionFind = new UnionFind(m, n);
List<Integer> ans = new LinkedList<>();
for (int[] position : positions) {
ans.add(unionFind.connect(position[0], position[1]));
}
return ans;
}
public static class UnionFind {
public int[] parents;
public int[] size;
public int[] help;
public int sets;
public int row;
public int col;
public UnionFind(int m, int n) {
row = m;
col = n;
sets = 0;
parents = new int[row * col];
size = new int[row * col];
help = new int[row * col];
}
public int sets() {
return sets;
}
public int index(int i, int j) {
return i * col + j;
}
public int findFather(int cur) {
int count = 0;
while (cur != parents[cur]) {
help[count++] = cur;
cur = parents[cur];
}
for (int i = 0; i < count; i++) {
parents[help[i]] = cur;
}
return cur;
}
public void union(int i1, int j1, int i2, int j2) {
if (i1 < 0 || i1 == row || j1 < 0 || j1 == col || i2 < 0 || i2 == row || j2 < 0 || j2 == col) {
return;
}
int index1 = index(i1, j1);
int index2 = index(i2, j2);
if (size[index1] == 0 || size[index2] == 0) {
return;
}
int f1 = findFather(index1);
int f2 = findFather(index2);
if (f1 != f2) {
int size1 = size[index1];
int size2 = size[index2];
int big = size1 > size2 ? f1 : f2;
int small = big == f1 ? f2 : f1;
parents[small] = big;
size[big] += size[small];
sets--;
}
}
public int connect(int i, int j) {
int index = index(i, j);
if (size[index] == 0) {
parents[index] = index;
size[index] = 1;
sets++;
union(i, j, i, j + 1);
union(i, j, i - 1, j);
union(i, j, i + 1, j);
union(i, j, i, j - 1);
}
return sets;
}
}
力扣链接:岛屿数量II
这里先简单的将一个矩形分一半来举例,示例图如下:
上述示例,1就表示岛屿,0表示海洋。如果不进行分割,那么岛屿的数量只有一个;如果进行分割,那么左边的岛屿数量是2,右边的岛屿数量也是2。
因此我们可以在分割后进行遍历后,将每个边界节点做一下记录,并给每个边界节点标好它自己的代表节点。当我们进行合并时,上述边界节点就分成了 a、b、c、d 四个集合,因此可以使用并查集,将这些集合进行合并,最终随着合并,岛屿的数量就变成了1个。
而对于 matrix 极大的情况,就可以进行多次分割,这时只要按照分割的方式,记录好边界点,并标好边界节点的代表节点,当合并时,使用并查集就可以依次合并!
版权说明 : 本文为转载文章, 版权归原作者所有 版权申明
原文链接 : https://t4dmw.blog.csdn.net/article/details/123209545
内容来源于网络,如有侵权,请联系作者删除!