力扣原题链接：岛屿数量
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1：
输入：grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
输出：1
示例 2：
输入：grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
输出：3
提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 300
gridi 的值为 '0' 或 '1'
package com.harrison.class10;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Stack;
/**
* @author Harrison
* @create 2022-03-19-16:46
* @motto 众里寻他千百度，蓦然回首，那人却在灯火阑珊处。
*/
public class Code03_NumberOfIslands {
// https://leetcode.com/problems/number-of-islands/
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++){
if(board[i][j]=='1'){
islands++;
infect(board,i,j);
}
}
}
return islands;
}
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]=2;
infect(board,i-1,j);
infect(board,i+1,j);
infect(board,i,j-1);
infect(board,i,j+1);
}
public static int numIslands1(char[][] board){
int row=board.length;
int col=board[0].length;
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);
for(int j=1; j<col; j++){
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();
}
public static class Dot{
}
public static class Node<V>{
public V value;
public Node(V v){
value=v;
}
}
public static class UnionFind1<V>{
public HashMap<V,Node<V>> nodes;
public HashMap<Node<V>,Node<V>> parent;
public HashMap<Node<V>,Integer> sizeMap;
public UnionFind1(List<V> values){
nodes=new HashMap<>();
parent=new HashMap<>();
sizeMap=new HashMap<>();
for(V cur:values){
Node<V> node=new Node<>(cur);
nodes.put(cur,node);
parent.put(node,node);
sizeMap.put(node,1);
}
}
public Node<V> findAncestor(Node<V> cur){
Stack<Node<V>> path=new Stack<>();
while (cur!=parent.get(cur)){
path.push(cur);
cur=parent.get(cur);
}
while (!path.isEmpty()){
parent.put(path.pop(),cur);
}
return cur;
}
public void union(V a,V b){
Node<V> aHead=findAncestor(nodes.get(a));
Node<V> bHead=findAncestor(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=aHead==big?bHead:aHead;
parent.put(small,big);
sizeMap.put(big,aSetSize+bSetSize);
sizeMap.remove(small);
}
}
public int sets(){
return sizeMap.size();
}
}
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{
public int[] parent;
public int[] size;
public int[] help;
public int col;
public int sets;
public UnionFind2(char[][] board){
int row=board.length;
col=board[0].length;
sets=0;
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++;
}
}
}
}
// (i,j) -> i*列数+j
public int index(int r,int c) {
return r*col+c;
}
// 原始位置 -> 下标
public 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;
}
}
// 为了测试
public static char[][] generateRandomMatrix(int row, int col) {
char[][] board = new char[row][col];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
board[i][j] = Math.random() < 0.5 ? '1' : '0';
}
}
return board;
}
// 为了测试
public static char[][] copy(char[][] board) {
int row = board.length;
int col = board[0].length;
char[][] ans = new char[row][col];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
ans[i][j] = board[i][j];
}
}
return ans;
}
// 为了测试
public static void main(String[] args) {
int row = 0;
int col = 0;
char[][] board1 = null;
char[][] board2 = null;
char[][] board3 = null;
long start = 0;
long end = 0;
row = 1000;
col = 1000;
board1 = generateRandomMatrix(row, col);
board2 = copy(board1);
board3 = copy(board1);
System.out.println("感染方法、并查集(map实现)、并查集(数组实现)的运行结果和运行时间");
System.out.println("随机生成的二维矩阵规模 : " + row + " * " + col);
start = System.currentTimeMillis();
System.out.println("感染方法的运行结果: " + numIslands3(board1));
end = System.currentTimeMillis();
System.out.println("感染方法的运行时间: " + (end - start) + " ms");
start = System.currentTimeMillis();
System.out.println("并查集(map实现)的运行结果: " + numIslands1(board2));
end = System.currentTimeMillis();
System.out.println("并查集(map实现)的运行时间: " + (end - start) + " ms");
start = System.currentTimeMillis();
System.out.println("并查集(数组实现)的运行结果: " + numIslands2(board3));
end = System.currentTimeMillis();
System.out.println("并查集(数组实现)的运行时间: " + (end - start) + " ms");
System.out.println();
row = 10000;
col = 10000;
board1 = generateRandomMatrix(row, col);
board3 = copy(board1);
System.out.println("感染方法、并查集(数组实现)的运行结果和运行时间");
System.out.println("随机生成的二维矩阵规模 : " + row + " * " + col);
start = System.currentTimeMillis();
System.out.println("感染方法的运行结果: " + numIslands3(board1));
end = System.currentTimeMillis();
System.out.println("感染方法的运行时间: " + (end - start) + " ms");
start = System.currentTimeMillis();
System.out.println("并查集(数组实现)的运行结果: " + numIslands2(board3));
end = System.currentTimeMillis();
System.out.println("并查集(数组实现)的运行时间: " + (end - start) + " ms");
}
}
