LeetCode Python - 59. 螺旋矩阵 II
目录
- 题目描述
- 解法
- 运行结果
题目描述
给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
示例 1：
输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]
示例 2：
输入：n = 1
输出：[[1]]
提示：
- 1 <= n <= 20
解法
模拟
直接模拟螺旋矩阵的生成过程。
定义一个二维数组 ans，用于存储螺旋矩阵。用 i 和 j 分别表示当前位置的行号和列号，用 k 表示当前的方向编号，dirs 表示方向编号与方向的对应关系。
从 1 开始，依次填入矩阵中的每个位置。每次填入一个位置后，计算下一个位置的行号和列号，如果下一个位置不在矩阵中或者已经被填过，则改变方向，再计算下一个位置的行号和列号。
时间复杂度 O(n 2 )，其中 n 是矩阵的边长。忽略输出数组不计，空间复杂度 O(1)。
class Solution(object):
def generateMatrix(self, n):
"""
:type n: int
:rtype: List[List[int]]
"""
ans = [[0] * n for _ in range(n)]
dirs = ((0, 1), (1, 0), (0, -1), (-1, 0))
i = j = k = 0
for v in range(1, n * n + 1):
ans[i][j] = v
x, y = i + dirs[k][0], j + dirs[k][1]
if x < 0 or y < 0 or x >= n or y >= n or ans[x][y]:
k = (k + 1) % 4
x, y = i + dirs[k][0], j + dirs[k][1]
i, j = x, y
return ans
运行结果
