【Leetcode】305.岛屿数量II（困难）

1、题目

题目见【Leetcode】305.岛屿数量II（困难）

2、思路

每有一个位置改变为1的时候，就查看它的四个相邻位置（上下左右）是否能合并，最后计算集合的数量。

3、代码

Java 版

public class NumberOfIslandsII {
    
	//方法一：【时间复杂度】O(m*n) + O(k) ，其中 O(m*n) 是初始化，而 O(k) 是多少个位置要修改为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; //size[i] != 0，表示 i 位置已经被初始化，否则表示没有被初始化
		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;
		}

		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);
            //注意被合并的集合的size不需要更改，因为要用它来标记是否初始化
			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 connect(int r, int c) {
     //[r,c]位置修改为1
			int index = index(r, c);//得到该位置在一维数组中的下标
			if (size[index] == 0) {
    //为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;
		}

	}
	
	//方法二：
	// 如果m*n比较大，会经历很重的初始化，而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;
	}
	
    // 如果（17,1009）要修改为1，那么用字符串 “17_1009” 代替它
    //不用初始化的时候就那么大的空间，动态增加
	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;
		}

	}
}