螺旋矩阵

题目描述

给定一个 m x n 的矩阵 matrix ，请按照顺时针螺旋顺序，返回矩阵中的所有元素。

示例

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]

解题思路

自做

拿到题的时候我用iPad画了一下，想到了模拟螺旋的过程，通过四个方向的限制来模拟螺旋的过程。

// 0ms
func spiralOrder(matrix [][]int) []int {
    // 获取矩阵的行数和列数
    m, n := len(matrix), len(matrix[0])
    // 计算矩阵的元素个数
    all := m * n
    // 定义起始位置的坐标
    x, y := 0, 0
    // 定义四个方向的限制
    limitX, limitMaxX, limitY, limitMaxY := 1, m, 0, n
    // 定义一个切片用于存储结果
    var s []int
    // 定义一个变量用于存储方向
    direct := 0
    // 循环遍历矩阵
    for i := 0; i < all; i++ {
        // 将矩阵的元素存入切片
        s = append(s, matrix[x][y])
        switch direct {
        // 向右
        case 0:
            if y == limitMaxY-1 {
                direct = 1
                x++
                limitMaxY--
            } else {
                y++
            }
        // 向下
        case 1:
            if x == limitMaxX-1 {
                direct = 2
                y--
                limitMaxX--
            } else {
                x++
            }
        // 向左
        case 2:
            if y == limitY {
                direct = 3
                x--
                limitY++
            } else {
                y--
            }
        // 向上
        case 3:
            if x == limitX {
                direct = 0
                y++
                limitX++
            } else {
                x--
            }
        }
    }
    return s
}

学习

方法一：模拟 可以模拟螺旋矩阵的路径。初始位置是矩阵的左上角，初始方向是向右，当路径超出界限或者进入之前访问过的位置时，顺时针旋转，进入下一个方向。

判断路径是否进入之前访问过的位置需要使用一个与输入矩阵大小相同的辅助矩阵 visited，其中的每个元素表示该位置是否被访问过。当一个元素被访问时，将 visited 中的对应位置的元素设为已访问。

如何判断路径是否结束？由于矩阵中的每个元素都被访问一次，因此路径的长度即为矩阵中的元素数量，当路径的长度达到矩阵中的元素数量时即为完整路径，将该路径返回。

func spiralOrder(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
}

官方给出的解法一引入了一个visited数组，用于标记已经访问过的元素，通过directions数组来控制方向，通过directionIndex来控制方向的变化。

方法二：按层模拟 可以将矩阵看成若干层，首先输出最外层的元素，其次输出次外层的元素，直到输出最内层的元素。

定义矩阵的第 k 层是到最近边界距离为 k 的所有顶点。例如，下图矩阵最外层元素都是第 1 层，次外层元素都是第 2 层，剩下的元素都是第 3 层。

[[1, 1, 1, 1, 1, 1, 1], 1, 2, 2, 2, 2, 2, 1, 1, 2, 3, 3, 3, 2, 1, 1, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] 对于每层，从左上方开始以顺时针的顺序遍历所有元素。假设当前层的左上角位于 (top,left)，右下角位于 (bottom,right)，按照如下顺序遍历当前层的元素。

从左到右遍历上侧元素，依次为 (top,left) 到 (top,right)。

从上到下遍历右侧元素，依次为 (top+1,right) 到 (bottom,right)。

如果 left<right 且 top<bottom，则从右到左遍历下侧元素，依次为 (bottom,right−1) 到 (bottom,left+1)，以及从下到上遍历左侧元素，依次为 (bottom,left) 到 (top+1,left)。

遍历完当前层的元素之后，将 left 和 top 分别增加 1，将 right 和 bottom 分别减少 1，进入下一层继续遍历，直到遍历完所有元素为止。

func spiralOrder(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
}

总结

今天刷了一道中等难度的题目，螺旋矩阵。自己的解法是模拟螺旋的过程，通过四个方向的限制来模拟螺旋的过程。

感觉官方的解法比较麻烦，而且代码不容易看懂，自己的解法比较简单，但是需要注意边界的问题。

通过这道题目，学习了模拟螺旋矩阵的过程，以及按层模拟的方法。

明天继续刷题，加油！