作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
备注说明：方便大家阅读，统一使用python，带必要注释，公众号 数据分析螺丝钉 一起打怪升级
题目描述
给你一个正整数 n，生成一个包含 1 到 n^2 所有元素的 n x n 正方形矩阵，数组的元素按螺旋顺序依次填充。
输入格式
- n：一个正整数，表示矩阵的大小。
输出格式
- 返回一个
n x n的数组，按螺旋顺序填充从1到n^2的整数。
示例 1
输入: n = 3 输出: [[1,2,3],[8,9,4],[7,6,5]]
方法一：模拟螺旋填充
解题步骤
- 初始化矩阵：创建一个
n x n的矩阵，初始填充值为0。 - 螺旋遍历：定义四个方向，模拟螺旋遍历的过程，按顺序填入数字。
- 边界条件处理：在填充过程中，需要不断检查下一个位置是否超出边界或已被填充。
完整的规范代码
def generateMatrix(n): """ 使用模拟螺旋遍历的方法生成螺旋矩阵 :param n: int, 矩阵的大小 :return: List[List[int]], 螺旋矩阵 """ matrix = [[0] * n for _ in range(n)] directions = [(0, 1), (1, 0), (0, -1), (-1, 0)] # right, down, left, up row, col, di = 0, 0, 0 for i in range(1, n*n + 1): matrix[row][col] = i dr, dc = directions[di] if not (0 <= row + dr < n and 0 <= col + dc < n and matrix[row + dr][col + dc] == 0): di = (di + 1) % 4 # Change direction dr, dc = directions[di] row, col = row + dr, col + dc return matrix # 示例调用 print(generateMatrix(3)) # 输出: [[1, 2, 3], [8, 9, 4], [7, 6, 5]]
算法分析
- 时间复杂度：(O(n^2))，其中
n是矩阵的维度，需要填充n^2个元素。 - 空间复杂度：(O(n^2))，用于存储生成的矩阵。
方法二：分层填充法
解题步骤
- 定义边界：设置上下左右四个边界，控制填充范围。
- 外层到内层填充：按层模拟填充过程，每完成一圈缩小填充范围。
- 逐层填充：按照右下左上的顺序逐层填充，每填完一全圈，四个边界向内缩进。
完整的规范代码
def generateMatrix(n): """ 使用分层填充法生成螺旋矩阵 :param n: int, 矩阵的大小 :return: List[List[int]], 螺旋矩阵 """ matrix = [[0] * n for _ in range(n)] left, right, top, bottom = 0, n-1, 0, n-1 num = 1 while left <= right and top <= bottom: for i in range(left, right + 1): matrix[top][i] = num num += 1 top += 1 for i in range(top, bottom + 1): matrix[i][right] = num num += 1 right -= 1 if top <= bottom: for i in range(right, left - 1, -1): matrix[bottom][i] = num num += 1 bottom -= 1 if left <= right: for i in range(bottom, top - 1, -1): matrix[i][left] = num num += 1 left += 1 return matrix # 示例调用 print(generateMatrix(3)) # 输出: [[1, 2, 3], [8, 9, 4], [7, 6, 5]]
算法分析
- 时间复杂度：(O(n^2))，必须填充所有
n^2个元素。 - 空间复杂度：(O(n^2))，用于存储生成的矩阵。
方法三：递归填充
解题步骤
- 递归函数定义：定义一个递归函数用于填充每一层。
- 递归填充：从外层向内层递归填充，每次递归填充一圈。
- 终止条件：当填充完成或只剩下一行/一列时终止递归。
完整的规范代码
def generateMatrix(n): """ 使用递归方法生成螺旋矩阵 :param n: int, 矩阵的大小 :return: List[List[int]], 螺旋矩阵 """ matrix = [[0] * n for _ in range(n)] fill(matrix, 0, n, 1) return matrix def fill(matrix, start, n, val): if n <= 0: return if n == 1: matrix[start][start] = val return for i in range(n - 1): matrix[start][start + i] = val val += 1 for i in range(n - 1): matrix[start + i][start + n - 1] = val val += 1 for i in range(n - 1): matrix[start + n - 1][start + n - 1 - i] = val val += 1 for i in range(n - 1): matrix[start + n - 1 - i][start] = val val += 1 fill(matrix, start + 1, n - 2, val) # 示例调用 print(generateMatrix(3)) # 输出: [[1, 2, 3], [8, 9, 4], [7, 6, 5]]
算法分析
- 时间复杂度：(O(n^2))，需要填充所有
n^2个元素。 - 空间复杂度：(O(n^2))，用于存储生成的矩阵，加上递归栈的开销（最坏情况下为 (O(n))）。
方法四：迭代展开
解题步骤
- 初始化变量：定义矩阵、起始点、方向等变量。
- 迭代填充：通过迭代的方式填充矩阵，类似于方法一但避免了方向切换的复杂判断。
- 边界处理：在迭代中处理矩阵边界和已填充元素的情况。
完整的规范代码
def generateMatrix(n): """ 使用迭代展开的方法生成螺旋矩阵 :param n: int, 矩阵的大小 :return: List[List[int]], 螺旋矩阵 """ matrix = [[0] * n for _ in range(n)] x, y, dx, dy = 0, 0, 0, 1 for i in range(1, n*n+1): matrix[x][y] = i if matrix[(x+dx)%n][(y+dy)%n]: dx, dy = dy, -dx x, y = x + dx, y + dy return matrix # 示例调用 print(generateMatrix(3)) # 输出: [[1, 2, 3], [8, 9, 4], [7, 6, 5]]
算法分析
- 时间复杂度：(O(n^2))，需要填充所有
n^2个元素。 - 空间复杂度：(O(n^2))，用于存储生成的矩阵。
方法五：分治填充
解题步骤
- 定义填充函数：创建一个函数用于填充矩阵的一圈。
- 分治递归：递归地填充外圈后，对内层矩阵进行相同操作。
- 终止与初始化：当矩阵大小减小到1或0时终止递归。
完整的规范代码
def generateMatrix(n): """ 使用分治填充法生成螺旋矩阵 :param n: int, 矩阵的大小 :return: List[List[int]], 螺旋矩阵 """ matrix = [[0] * n for _ in range(n)] fill_layer(matrix, 0, n, 1) return matrix def fill_layer(matrix, start, size, start_val): if size <= 0: return if size == 1: matrix[start][start] = start_val return # Fill the perimeter for i in range(size - 1): matrix[start][start+i] = start_val start_val += 1 for i in range(size - 1): matrix[start+i][start+size-1] = start_val start_val += 1 for i in range(size - 1): matrix[start+size-1][start+size-1-i] = start_val start_val += 1 for i in range(size - 1): matrix[start+size-1-i][start] = start_val start_val += 1 fill_layer(matrix, start+1, size-2, start_val) # 示例调用 print(generateMatrix(3)) # 输出: [[1, 2, 3], [8, 9, 4], [7, 6, 5]]
算法分析
- 时间复杂度：(O(n^2))，需要填充所有
n^2个元素。 - 空间复杂度：(O(n^2))，用于存储生成的矩阵，递归栈深度依矩阵大小而定。
不同算法的优劣势对比
| 特征 | 方法一: 模拟螺旋填充 | 方法二: 分层填充法 | 方法三: 递归填充 | 方法四: 迭代展开 | 方法五: 分治填充 |
| 时间复杂度 | (O(n^2)) | (O(n^2)) | (O(n^2)) | (O(n^2)) | (O(n^2)) |
| 空间复杂度 | (O(n^2)) | (O(n^2)) | (O(n^2)) | (O(n^2)) | (O(n^2)) |
| 优势 | 直观易理解 | 清晰结构化 | 结构简单 | 代码简洁 | 递归清晰，易于理解 |
| 劣势 | 稍微复杂的控制流 | 多次循环 | 递归深度问题 | 边界处理复杂 | 空间使用多，递归深度 |
应用示例
游戏开发：
在游戏开发中，尤其是需要生成迷宫或特定图案的场景设计里，螺旋矩阵可以用于设计关卡的地图布局，例如生成螺旋迷宫地图，增加游戏的趣味性和挑战性。
通过上述方法，开发者可以选择最适合其应用场景的算法来实现高效、可靠的矩阵生成功能。
欢迎关注微信公众号 数据分析螺丝钉
