2020年09月03日:裸写算法:回形矩阵遍历。

福哥答案2020年09月03日:

方法一:模拟,位图方式。
跟 方法二 一样,区别是辅助矩阵visited用位图节约空间。

方法二:模拟。
可以模拟螺旋矩阵的路径。初始位置是矩阵的左上角,初始方向是向右,当路径超出界限或者进入之前访问过的位置时,则顺时针旋转,进入下一个方向。
判断路径是否进入之前访问过的位置需要使用一个与输入矩阵大小相同的辅助矩阵visited,其中的每个元素表示该位置是否被访问过。当一个元素被访问时,将 visited 中的对应位置的元素设为已访问。
如何判断路径是否结束?由于矩阵中的每个元素都被访问一次,因此路径的长度即为矩阵中的元素数量,当路径的长度达到矩阵中的元素数量时即为完整路径,将该路径返回。
复杂度分析
时间复杂度:O(mn),其中 m 和 n 分别是输入矩阵的行数和列数。矩阵中的每个元素都要被访问一次。
空间复杂度:O(mn)。需要创建一个大小为 ×ばつn 的矩阵 visited 记录每个位置是否被访问过。

方法三:按层模拟
可以将矩阵看成若干层,首先输出最外层的元素,其次输出次外层的元素,直到输出最内层的元素。
定义矩阵的第 k 层是到最近边界距离为 k 的所有顶点。例如,下图矩阵最外层元素都是第 1 层,次外层元素都是第 2 层,剩下的元素都是第 3 层。
复杂度分析
时间复杂度:O(mn),其中 m 和 n 分别是输入矩阵的行数和列数。矩阵中的每个元素都要被访问一次。
空间复杂度:O(1)。除了输出数组以外,空间复杂度是常数。

代码用golang编写,如下:

package test37_spiralorder
import (
 "fmt"
 "testing"
)
//https://leetcode-cn.com/problems/spiral-matrix/solution/luo-xuan-ju-zhen-by-leetcode-solution/
//go test -v -test.run TestSpiralOrder
func TestSpiralOrder(t *testing.T) {
 const N = 3
 matrix := make([][]int, N)
 for i := 0; i < N; i++ {
 matrix[i] = make([]int, N)
 for j := 0; j < N; j++ {
 matrix[i][j] = i*N + j + 1
 }
 }
 fmt.Println(matrix)
 ret := spiralOrder1(matrix)
 fmt.Println(ret, "方法一:模拟,位图")
 ret = spiralOrder2(matrix)
 fmt.Println(ret, "方法二:模拟")
 ret = spiralOrder3(matrix)
 fmt.Println(ret, "方法三:按层模拟")
}
//方法一:模拟,位图
func spiralOrder1(matrix [][]int) []int {
 if len(matrix) == 0 || len(matrix[0]) == 0 {
 return []int{}
 }
 rows, columns := len(matrix), len(matrix[0])
 visited := make([]byte, (rows*columns+7)/8)
 var (
 total = rows * columns
 order = make([]int, total)
 row, column = 0, 0
 directions = [][]int{[]int{0, 1}, []int{1, 0}, []int{0, -1}, []int{-1, 0}}
 directionIndex = 0
 )
 for i := 0; i < total; i++ {
 order[i] = matrix[row][column]
 SetBitMapValue(visited, row*columns+column, true)
 nextRow, nextColumn := row+directions[directionIndex][0], column+directions[directionIndex][1]
 if nextRow < 0 ||
 nextRow >= rows ||
 nextColumn < 0 ||
 nextColumn >= columns ||
 GetBitMapValue(visited, nextRow*columns+nextColumn) {
 directionIndex = (directionIndex + 1) % 4
 }
 row += directions[directionIndex][0]
 column += directions[directionIndex][1]
 }
 return order
}
//方法二:模拟
func spiralOrder2(matrix [][]int) []int {
 if len(matrix) == 0 || len(matrix[0]) == 0 {
 return []int{}
 }
 rows, columns := len(matrix), len(matrix[0])
 visited := make([][]bool, rows)
 for i := 0; i < rows; i++ {
 visited[i] = make([]bool, columns)
 }
 var (
 total = rows * columns
 order = make([]int, total)
 row, column = 0, 0
 directions = [][]int{[]int{0, 1}, []int{1, 0}, []int{0, -1}, []int{-1, 0}}
 directionIndex = 0
 )
 for i := 0; i < total; i++ {
 order[i] = matrix[row][column]
 visited[row][column] = true
 nextRow, nextColumn := row+directions[directionIndex][0], column+directions[directionIndex][1]
 if nextRow < 0 || nextRow >= rows || nextColumn < 0 || nextColumn >= columns || visited[nextRow][nextColumn] {
 directionIndex = (directionIndex + 1) % 4
 }
 row += directions[directionIndex][0]
 column += directions[directionIndex][1]
 }
 return order
}
//方法三:按层模拟
func spiralOrder3(matrix [][]int) []int {
 if len(matrix) == 0 || len(matrix[0]) == 0 {
 return []int{}
 }
 var (
 rows, columns = len(matrix), len(matrix[0])
 order = make([]int, rows*columns)
 index = 0
 left, right, top, bottom = 0, columns - 1, 0, rows - 1
 )
 for left <= right && top <= bottom {
 for column := left; column <= right; column++ {
 order[index] = matrix[top][column]
 index++
 }
 for row := top + 1; row <= bottom; row++ {
 order[index] = matrix[row][right]
 index++
 }
 if left < right && top < bottom {
 for column := right - 1; column > left; column-- {
 order[index] = matrix[bottom][column]
 index++
 }
 for row := bottom; row > top; row-- {
 order[index] = matrix[row][left]
 index++
 }
 }
 left++
 right--
 top++
 bottom--
 }
 return order
}
//获取位图第index元素的值
func GetBitMapValue(data []byte, index int) bool {
 return data[index/8]&(1<<(index%8)) != 0
}
//设置位图第index元素的值
func SetBitMapValue(data []byte, index int, v bool) {
 if v {
 data[index/8] |= 1 << (index % 8)
 } else {
 data[index/8] &= ^(1 << (index % 8))
 }
}

敲 go test -v -test.run TestSpiralOrder 命令,结果如下:

评论

本文来自:简书

感谢作者:福大大架构师每日一题

查看原文:2020年09月03日:裸写算法:回形矩阵遍历。

• 编辑
• 预览