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 grid[0][1] 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 grid[2][1] 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?
一个由m行和n列组成的二维网格图最初是用水填充的。我们可以执行一个加法运算，把位置（行，列）的水变成一个陆地。给定一个要操作的位置列表，计算每个addland操作后的岛数。岛屿被水环绕，由水平或垂直连接相邻土地形成。您可以假设网格的所有四个边缘都被水包围。
例子：
给定 m = 3, n = 3, positions = [[0,0], [0,1], [1,2], [2,1]].
最初，二维网格充满了水。（假设0代表水，1代表土地）。
0 0 0 0 0 0 0 0 0
操作1:addland（0，0）将网格[0][0]处的水变成陆地。
1 0 0 0 0 0 岛屿个数 = 1 0 0 0
操作2:addland（0，1）将网格[0][1]处的水转化为陆地。
1 1 0 0 0 0 岛屿个数 = 1 0 0 0
操作3:addland（1，2）将网格[1][2]处的水变成陆地。
1 1 0 0 0 1 岛屿个数 = 2 0 0 0
操作4:addland（2，1）将网格[2][1]处的水变成陆地。
1 1 0 0 0 1 岛屿个数 = 3 0 1 0
我们以数组的形式返回结果：[1，1，2，3]
挑战：
你能在时间复杂度o（k log mn）中做到吗？k是位置的长度？
Solution:
1 class Solution {
2 func numIslands2(_ m:Int,_ n:Int,_ positions:inout [[Int]]) ->[Int] {
3 var res:[Int] = [Int]()
4 var cnt:Int = 0
5 var roots:[Int] = [Int](repeating:-1,count:m * n)
6 var dirs:[[Int]] = [[0, -1],[-1, 0],[0, 1],[1, 0]]
7 for a in positions
8 {
9 var id:Int = n * a[0] + a[1]
10 if roots[id] == -1
11 {
12 roots[id] = id
13 cnt += 1
14 }
15 for dir in dirs
16 {
17 var x:Int = a[0] + dir[0]
18 var y:Int = a[1] + dir[1]
19 var cur_id:Int = n * x + y
20 if x < 0 || x >= m || y < 0 || y >= n || roots[cur_id] == -1
21 {
22 continue
23 }
24 var p:Int = findRoot(&roots, cur_id)
25 var q:Int = findRoot(&roots, id)
26 if p != q
27 {
28 roots[p] = q
29 cnt -= 1
30 }
31 }
32 res.append(cnt)
33 }
34 return res
35 }
36
37 func findRoot(_ roots:inout [Int],_ id:Int) -> Int
38 {
39 return (id == roots[id]) ? id : findRoot(&roots, roots[id])
40 }
41 }
点击：Playground测试
1 var sol = Solution() 2 let m:Int = 3 3 let n:Int = 3 4 var positions:[[Int]] = [[0,0], [0,1], [1,2], [2,1]] 5 print(sol.numIslands2(m,n,&positions)) 6 //Print [1, 1, 2, 3]