[Swift]LeetCode305. 岛屿的个数 II $ Number of Islands II

概述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

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 00 0 00 0 0

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

1 0 00 0 0   Number of islands = 10 0 0

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

1 1 00 0 0   Number of islands = 10 0 0

Operation #3: addLand(1,2) turns the water at grID[1][2] into a land.

1 1 00 0 1   Number of islands = 20 0 0

Operation #4: addLand(2,1) turns the water at grID[2][1] into a land.

1 1 00 0 1   Number of islands = 30 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,1]].

最初，二维网格充满了水。（假设0代表水，1代表土地）。

0 0 00 0 00 0 0

*** 作1:addland（0，0）将网格[0][0]处的水变成陆地。

1 0 00 0 0   岛屿个数 = 10 0 0

*** 作2:addland（0，1）将网格[0][1]处的水转化为陆地。

1 1 00 0 0   岛屿个数 = 10 0 0

*** 作3:addland（1，2）将网格[1][2]处的水变成陆地。

1 1 00 0 1   岛屿个数 = 20 0 0

*** 作4:addland（2，1）将网格[2][1]处的水变成陆地。

1 1 00 0 1   岛屿个数 = 30 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] == -111             {12                 roots[ID] = ID13                 cnt += 114             }15             for dir in dirs16             {17                 var x:Int = a[0] + dir[0]18                 var y:Int = a[1] + dir[1]19                 var cur_ID:Int = n * x + y20                 if x < 0 || x >= m || y < 0 || y >= n || roots[cur_ID] == -121                 {22                     continue23                 }24                 var p:Int = findRoot(&roots,cur_ID)25                 var q:Int = findRoot(&roots,ID)26                 if p != q27                 {28                     roots[p] = q29                     cnt -= 130                 }31             }32             res.append(cnt)33         }34         return res        35     }36     37     func findRoot(_ roots:inout [Int],_ ID:Int) -> Int38     {39         return (ID == roots[ID]) ? ID : findRoot(&roots,roots[ID])40     }41 }

点击：Playground测试

1 var sol = Solution()2 let m:Int = 33 let n:Int = 34 var positions:[[Int]] = [[0,2],[2,1]]5 print(sol.numIslands2(m,n,&positions))6 //Print [1,3]

总结

以上是内存溢出为你收集整理的[Swift]LeetCode305. 岛屿的个数 II $ Number of Islands II全部内容，希望文章能够帮你解决[Swift]LeetCode305. 岛屿的个数 II $ Number of Islands II所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。