leetcode解题: Number of Islands II (305)

发表于 | 分类于

A 2d grid map of m rows and n columns is initially filled with water. We may perform an addLand operation which turns the water at position (row, col) into a land. Given a list of positions to operate, count the number of islands after each addLand operation. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example:

Given m = 3, n = 3, positions = [[0,0], [0,1], [1,2], [2,1]].
Initially, the 2d grid grid is filled with water. (Assume 0 represents water and 1 represents land).

0 0 0
0 0 0
0 0 0
Operation #1: addLand(0, 0) turns the water at grid[0][0] into a land.

1 0 0
0 0 0 Number of islands = 1
0 0 0
Operation #2: addLand(0, 1) turns the water at grid0 into a land.

1 1 0
0 0 0 Number of islands = 1
0 0 0
Operation #3: addLand(1, 2) turns the water at grid[1][2] into a land.

1 1 0
0 0 1 Number of islands = 2
0 0 0
Operation #4: addLand(2, 1) turns the water at grid2 into a land.

1 1 0
0 0 1 Number of islands = 3
0 1 0
We return the result as an array: [1, 1, 2, 3]

Challenge:

Can you do it in time complexity O(k log mn), where k is the length of the positions?

解法1：Union Find O(k logmn)

这是一题难题了，为了熟悉Union Find的算法也做（抄）一下吧。主要是参考了这篇.
Union Find很适合用来解决两点是否想通的问题。用一个roots来记录每一个点的group id也就是下面code中的parent。
然后对于每一个插入的点，首先把自己的点的group id设为自己，然后搜索周围相邻的点，如果相邻的点是陆地并且相邻的点的group id和自己不同的时候，则说明需要进行Union操作。
这个时候对于当前岛屿的数量需要-1，因为合并了一个。
Java

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
45
46
47
48
public class Solution {
    
	private int[][] directions = {{0,1},{0,-1},{1,0},{-1,0}};
	public List<Integer> numIslands2(int m, int n, int[][] positions) {
		// Union Find
		List<Integer> result = new ArrayList<Integer>();
		if (m <= 0 || n <= 0 || positions.length == 0 || positions[0].length == 0) {
			return result;
		}
		
		int count = 0;
		int[] roots = new int[m * n];
		Arrays.fill(roots, -1);
		for (int[] position: positions) {
			// positions
			count++;
			int index = n * position[0] + position[1];
			roots[index] = index;
			// perform union operations
			for (int[] direction: directions) {
				int x = position[0] + direction[0];
				int y = position[1] + direction[1];
				int neighbor = x * n + y;
				if ( x < 0 || x >= m || y < 0 || y >= n || roots[neighbor] == -1) {
					continue;
				}
				int parent = find(roots, neighbor);
				if (parent != index) {
					roots[index] = parent;
					count--;
					index = parent;
				}
			}
			result.add(count);
		}
		
		return result;
    }
	private int find(int[] roots, int index) {
		while (roots[index] != index) {
			index = roots[index];
		}
		return index;
	}		
}