题目链接:
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 是存储矩阵所需的空间。