LeetCode 面试题 16.19. 水域大小
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/group-anagrams/description/
博主Github：https://github.com/GDUT-Rp/LeetCode
题目：
你有一个用于表示一片土地的整数矩阵land，该矩阵中每个点的值代表对应地点的海拔高度。若值为0则表示水域。由垂直、水平或对角连接的水域为池塘。池塘的大小是指相连接的水域的个数。编写一个方法来计算矩阵中所有池塘的大小，返回值需要从小到大排序。
示例 1:
输入：
[[0,2,1,0],[0,1,0,1],[1,1,0,1],[0,1,0,1]
]
输出： [1,2,4]
提示：
- 0 < len(land) <= 1000
- 0 < len(land[i]) <= 1000
解题思路：
方法一：深度优先遍历
遍历矩阵 land \textit{land} land，如果当前遍历的点 ( i , j ) (i,j) (i,j) 满足 l a n d [ i ] [ j ] = 0 land[i][j]=0 land[i][j]=0，那么对 ( i , j ) (i,j) (i,j) 进行深度优先搜索，深度优先搜索的过程如下：
如果 ( i , j ) (i, j) (i,j) 越界或 land [ i ] [ j ] ≠ 0 \textit{land}[i][j] \ne 0 land[i][j]=0，直接返回 0。
令 land [ i ] [ j ] = − 1 \textit{land}[i][j] = -1 land[i][j]=−1，表示该点已经被搜索过，然后对该点的八个相邻点执行深度优先搜索。
返回值为执行的深度优先搜索的结果和加 1。
将所有结果放入一个数组内，然后从小到大进行排序，返回结果。
Golang
func pondSizes(land [][]int) []int {// dfsrowCount := len(land)columnCount := len(land[0])var dfs func(i, j int) intdfs = func(x, y int) int {// out of pointer || != waterif x < 0 || x >= rowCount || y < 0 || y >= columnCount {return 0}if land[x][y] != 0 {return 0}// markland[x][y] = -1res := 1for dx := -1; dx <= 1; dx++ {for dy := -1; dy <= 1; dy++ {// myselftif dx == 0 && dy == 0 {continue}res += dfs(x + dx , y + dy)}}return res}// sumvar res []intfor i := 0; i < rowCount; i++ {for j := 0; j < columnCount; j++ {if land[i][j] == 0 {res = append(res, dfs(i, j)) } }}// sortsort.Ints(res)return res
}复杂度分析
时间复杂度： O ( m n × log m n ) O(mn \times \log{mn}) O(mn×logmn)，其中 m m m 和 n n n 分别是矩阵 land \textit{land} land 的行数和列数。深度优先搜索需要 O ( m × n ) O(m \times n) O(m×n)，在最坏情况下，结果数组 res \textit{res} res 的大小为 m n mn mn 的量级，排序需要 O ( m n × log m n ) O(mn \times \log{mn}) O(mn×logmn)。
空间复杂度： O ( m × n ) O(m \times n) O(m×n)。返回值不计入空间复杂度，最坏情况下，深度优先搜索需要 O ( m × n ) O(m \times n) O(m×n) 的栈空间。
方法二：广度优先遍历
Golang
func pondSizes(land [][]int) []int {m, n := len(land), len(land[0])bfs := func(x, y int) int {q, res := [][]int{}, 0q, land[x][y] = append(q, []int{x, y}), -1for len(q) > 0 {x, y, q = q[0][0], q[0][1], q[1:]res++for dx := -1; dx <= 1; dx++ {for dy := -1; dy <= 1; dy++ {if dx == 0 && dy == 0 {continue}if x + dx < 0 || x + dx >= m || y + dy < 0 || y + dy >= n || land[x + dx][y + dy] != 0 {continue}land[x + dx][y + dy] = -1q = append(q, []int{x + dx, y + dy})}}}return res}res := []int{}for i := 0; i < m; i++ {for j := 0; j < n; j++ {if land[i][j] == 0 {res = append(res, bfs(i, j))}}}sort.Ints(res)return res
}复杂度分析
时间复杂度： O ( m n × log m n ) O(mn \times \log{mn}) O(mn×logmn)，其中 m m m 和 n n n 分别是矩阵 land \textit{land} land 的行数和列数。广度优先搜索需要 O ( m × n ) O(m \times n) O(m×n)，在最坏情况下，结果数组 res \textit{res} res 的大小为 m n mn mn 的量级，排序需要 O ( m n × log m n ) O(mn \times \log{mn}) O(mn×logmn)。
空间复杂度： O ( m + n ) O(m + n) O(m+n)。返回值不计入空间复杂度，最坏情况下，广度优先搜索需要 O ( m + n ) O(m + n) O(m+n) 的栈空间。
本文链接：https://my.lmcjl.com/post/13743.html
4 评论