LeetCode 59 螺旋矩阵 II

题目链接:

https://leetcode.cn/problems/spiral-matrix-ii/

以下是使用Go语言实现外观数列问题的代码:

func generateMatrix(n int) [][]int {
    // 创建一个 n x n 的矩阵
    matrix := make([][]int, n)
    for i := range matrix {
        matrix[i] = make([]int, n)
    }
    // 定义四个变量表示矩阵的上下左右边界
    top, bottom, left, right := 0, n-1, 0, n-1
    // 定义变量表示当前要填入的数字
    num := 1
    // 当上下边界相遇或左右边界相遇时结束循环
    for top <= bottom && left <= right {
        // 填充上边界从左到右
        for i := left; i <= right; i++ {
            matrix[top][i] = num
            num++
        }
        // 上边界向下收缩
        top++
        // 填充右边界从上到下
        for i := top; i <= bottom; i++ {
            matrix[i][right] = num
            num++
        }
        // 右边界向左收缩
        right--
        // 填充下边界从右到左
        for i := right; i >= left; i-- {
            matrix[bottom][i] = num
            num++
        }
        // 下边界向上收缩
        bottom--
        // 填充左边界从下到上
        for i := bottom; i >= top; i-- {
            matrix[i][left] = num
            num++
        }
        // 左边界向右收缩
        left++
    }
    return matrix
}

执行用时:0 ms, 在所有 Go 提交中击败了100.00%的用户

内存消耗:2 MB, 在所有 Go 提交中击败了8.81%的用户

通过测试用例:20 / 20

算法思路:

这道题目是一道经典的矩阵遍历问题,可以采用模拟的方法来解决。我们可以定义四个变量表示矩阵的上下左右边界,然后按照顺时针的顺序依次遍历矩阵的每一个位置,填入对应的数字。

具体来说,我们可以先创建一个 n x n 的矩阵,然后从左上角开始,先填充上边界从左到右,然后将上边界向下收缩,接着填充右边界从上到下,将右边界向左收缩,然后填充下边界从右到左,将下边界向上收缩,最后填充左边界从下到上,将左边界向右收缩,直到上下边界相遇或左右边界相遇为止。

时间复杂度分析:

遍历矩阵的每一个位置,时间复杂度为 O(n^2)。因此,总时间复杂度为 O(n^2)。

空间复杂度分析:

除了存储矩阵以外,我们只使用了常数个变量。因此,空间复杂度为 O(n^2)。其中,n^2 是存储矩阵所需的空间。

原文链接:,转发请注明来源!