September 3, 2020: naked writing algorithm: loop matrix traversal.

5 Line code , Can let wechat small program on the shelf to their own APP in | Register and send it to Dajiang 、 Huawei 、 Cherry keyboard ！>>>

Fogo's answer 2020-09-03：

Method 1 ： simulation , Bitmap mode .
Follow Method 2 equally , The difference is auxiliary matrix visited Save space with bitmaps .

Method 2 ： simulation .
You can simulate the path of a spiral matrix . The initial position is the upper left corner of the matrix , The initial direction is to the right , When a path goes out of bounds or enters a previously visited location , Turn clockwise , Go to the next direction .
To determine whether a path enters a previously visited location, an auxiliary matrix of the same size as the input matrix is required visited, Each of these elements indicates whether the location has been accessed . When an element is accessed , take visited Set the element at the corresponding position in the to be accessed .
How to judge whether the path is over ？ Because every element in the matrix is accessed once , So the length of the path is the number of elements in the matrix , When the length of the path reaches the number of elements in the matrix, it is a complete path , Return the path .
Complexity analysis
Time complexity ：O(mn), among m and n The number of rows and columns of the input matrix . Every element in the matrix is accessed once .
Spatial complexity ：O(mn). You need to create a size of m×n Matrix visited Record whether each location has been visited .

Method 3 ： Layer by layer simulation
You can think of a matrix as layers , First output the outermost element , Second, output the sub outer elements , Until the innermost element is output .
Define the order of a matrix k The distance from the layer to the nearest boundary is k All the vertices of . for example , The outermost elements of the matrix in the figure below are all the first 1 layer , The sub outer elements are the first 2 layer , The rest of the elements are the first 3 layer .
Complexity analysis
Time complexity ：O(mn), among m and n The number of rows and columns of the input matrix . Every element in the matrix is accessed once .
Spatial complexity ：O(1). In addition to the output array , Space complexity is a constant .

The code to use golang To write , as follows ：

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, " Method 1 ： simulation , Bitmap ")
    ret = spiralOrder2(matrix)
    fmt.Println(ret, " Method 2 ： simulation ")
    ret = spiralOrder3(matrix)
    fmt.Println(ret, " Method 3 ： Layer by layer simulation ")

}

// Method 1 ： simulation , Bitmap 
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
}

// Method 2 ： simulation 
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
}

// Method 3 ： Layer by layer simulation 
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
}

// Get bitmap No index The value of the element 
func GetBitMapValue(data []byte, index int) bool {
    return data[index/8]&(1<<(index%8)) != 0
}

// Set bitmap No index The value of the element 
func SetBitMapValue(data []byte, index int, v bool) {
    if v {
        data[index/8] |= 1 << (index % 8)
    } else {
        data[index/8] &= ^(1 << (index % 8))
    }
}

knock go test -v -test.run TestSpiralOrder command , give the result as follows ：

---

Comment on