59.螺旋矩阵II

一、问题描述

题目

给定一个正整数 n，生成一个包含 1 到 n^2 所有元素，且元素按顺时针螺旋排列的正方形矩阵。

示例

输入: 3
输出:
[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

二、方案一：模拟法

1、思路

模拟法是解决这类问题的直接方法。我们按照螺旋的顺序填充矩阵，即先填充上行从左到右，然后填充右列从上到下，接着填充下行从右到左，最后填充左列从下到上，如此循环直至填充完整个矩阵。

2、代码实现

func generateMatrix(n int) [][]int {
    matrix := make([][]int, n)
    for i := range matrix {
        matrix[i] = make([]int, n)
    }
    count, startx, starty, offset := 1, 0, 0, 1
    for n > 0 {
        i, j := startx, starty
        // 上行从左到右
        for j < starty + n - offset {
            matrix[startx][j] = count
            count++
            j++
        }
        // 右列从上到下
        for i < startx + n - offset {
            matrix[i][j] = count
            count++
            i++
        }
        // 下行从右到左
        for j > starty {
            matrix[i][j] = count
            count++
            j--
        }
        // 左列从下到上
        for i > startx {
            matrix[i][j] = count
            count++
            i--
        }
        startx++
        starty++
        n -= 2
    }
    return matrix
}

3、复杂度分析

• 时间复杂度：O(n^2)，其中 n 是给定的整数。我们需要填充整个 n x n 的矩阵。
• 空间复杂度：O(1)，我们没有使用额外的空间。

三、总结

模拟法是解决螺旋矩阵问题的有效方法。它通过模拟填充过程，直接生成所需的螺旋矩阵。这种方法在时间和空间复杂度上都是高效的，适合解决这类问题。