难度: Medium
给你一个正整数 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
难度: Medium
给你一个正整数 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
运行时间: 52 ms
内存: 14.9 MB
class Solution: def generateMatrix(self, n: int) -> List[List[int]]: ans = [[0]*n for _ in range(n)] l = 0 u = 0 d = n-1 r = n-1 num_to_fill = 1 while True: for i in range(l, r+1): ans[u][i] = num_to_fill num_to_fill += 1 u += 1 if u > d: break for i in range(u, d+1): ans[i][r] = num_to_fill num_to_fill += 1 r -= 1 if l > r: break for i in range(r, l-1, -1): ans[d][i] = num_to_fill num_to_fill += 1 d -= 1 if u > d: break for i in range(d, u-1, -1): ans[i][l] = num_to_fill num_to_fill += 1 l += 1 if l > r: break return ans
这个题解采用了模拟螺旋填充的方式来生成矩阵。通过控制矩阵的上下左右边界,依次填充矩阵的外围元素。具体步骤如下: 1. 初始化一个 n x n 的矩阵,元素全部为0。 2. 初始化矩阵的上下左右边界 u、d、l、r。 3. 从左到右填充上边界,更新上边界 u。 4. 从上到下填充右边界,更新右边界 r。 5. 从右到左填充下边界,更新下边界 d。 6. 从下到上填充左边界,更新左边界 l。 7. 重复步骤3-6,直到填充完整个矩阵。
时间复杂度: O(n^2)
空间复杂度: O(n^2)
```python class Solution: def generateMatrix(self, n: int) -> List[List[int]]: # 初始化一个 n x n 的矩阵,元素全部为0 ans = [[0]*n for _ in range(n)] # 初始化矩阵的上下左右边界 l = 0 u = 0 d = n-1 r = n-1 # 初始化要填充的元素值 num_to_fill = 1 while True: # 从左到右填充上边界 for i in range(l, r+1): ans[u][i] = num_to_fill num_to_fill += 1 u += 1 # 更新上边界 if u > d: break # 从上到下填充右边界 for i in range(u, d+1): ans[i][r] = num_to_fill num_to_fill += 1 r -= 1 # 更新右边界 if l > r: break # 从右到左填充下边界 for i in range(r, l-1, -1): ans[d][i] = num_to_fill num_to_fill += 1 d -= 1 # 更新下边界 if u > d: break # 从下到上填充左边界 for i in range(d, u-1, -1): ans[i][l] = num_to_fill num_to_fill += 1 l += 1 # 更新左边界 if l > r: break return ans ```
初始化矩阵时选择将所有元素设为0是因为0通常被视为一个清晰的占位符,它在视觉上容易区分已填充和未填充的区域。此外,0不在正整数范围内,这有助于在调试和验证过程中快速识别哪些位置尚未被更新。从实现的角度来看,使用列表推导式生成全0矩阵也是代码上的简洁实现。
在填充过程中,每一次更新边界如`u += 1`或`r -= 1`之后,都会通过循环的条件检查(如`if u > d`或`if l > r`)来确保填充操作不会进入已填充的区域。每次填充完一个边界后立即更新这个边界,并检查新的边界值是否导致了边界交叉,如果交叉则终止循环,这样就确保了不会有覆盖已填充元素的风险。这种方法依赖于严格的顺序和边界更新逻辑,保证了操作的安全性。
这些边界条件是基于矩阵填充的逻辑确定的。在螺旋填充矩阵时,如果上边界`u`超过了下边界`d`,或者左边界`l`超过了右边界`r`,这意味着已没有剩余空间需要填充,因此循环可以安全地中断。这种检查确保了只要存在可填充的区域,循环就会继续执行。因为这个逻辑严格遵守了矩阵的空间约束,所以它能覆盖所有可能的情况,确保算法在任意有效输入下都能正确完成工作。
是的,算法在设计时已经考虑到了所有从1到20的有效输入。由于算法内部的边界条件和填充逻辑确保了每次操作都是在安全的范围内进行,且每个元素只被填充一次,因此不需要在函数返回值前进行任何额外的检查或调整。这保证了算法的正确性和完整性,使其能夠在所有指定范围内的输入上正确运行。