作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
题目描述
给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。
输入格式
- matrix：一个二维整数数组，表示输入的矩阵。
输出格式
- 返回一个整数列表，表示矩阵按顺时针螺旋排序的结果。
示例
示例 1
输入: [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ] 输出: [1,2,3,6,9,8,7,4,5]
示例 2
输入: [ [1, 2, 3, 4], [5, 6, 7, 8], [9,10,11,12] ] 输出: [1,2,3,4,8,12,11,10,9,5,6,7]
方法一：模拟路径
解题步骤
- 边界控制：初始化上下左右边界，
top,bottom,left,right。 - 遍历矩阵：按照右、下、左、上的顺序遍历矩阵边界，按需调整各边界。
- 收缩边界：每完成一条边的遍历后，相应地收缩边界，继续循环，直到边界不合法。
完整的规范代码
def spiralOrder(matrix): """ 按顺时针螺旋顺序返回矩阵中的所有元素 :param matrix: List[List[int]], 输入的矩阵 :return: List[int], 螺旋顺序的元素列表 """ if not matrix: return [] result = [] top, bottom, left, right = 0, len(matrix) - 1, 0, len(matrix[0]) - 1 while True: # Traverse from left to right. for i in range(left, right + 1): result.append(matrix[top][i]) top += 1 if top > bottom: break # Traverse downwards. for i in range(top, bottom + 1): result.append(matrix[i][right]) right -= 1 if left > right: break # Traverse from right to left. for i in range(right, left - 1, -1): result.append(matrix[bottom][i]) bottom -= 1 if top > bottom: break # Traverse upwards. for i in range(bottom, top - 1, -1): result.append(matrix[i][left]) left += 1 if left > right: break return result # 示例调用 print(spiralOrder([[1, 2, 3], [4, 5, 6], [7, 8, 9]])) # 输出: [1,2,3,6,9,8,7,4,5]
算法分析
- 时间复杂度：(O(mn))，其中
m是矩阵的行数，n是矩阵的列数，我们需要遍历矩阵中的每个元素。 - 空间复杂度：(O(1))，除了输出数组外，额外使用的空间为常数。
方法二：分层模拟
解题步骤
- 分层处理：将矩阵看作若干层，外层到内层逐层处理。
- 按层遍历：每一层按顺时针方向遍历，注意处理最内层可能退化为一行或一列的情况。
- 边界调整：每处理完一层，调整对应的上下左右边界。
完整的规范代码
def spiralOrder(matrix): """ 分层模拟法按顺时针螺旋顺序返回矩阵中的所有元素 :param matrix: List[List[int]], 输入的矩阵 :return: List[int], 螺旋顺序的元素列表 """ result = [] while matrix: result += matrix.pop(0) if matrix and matrix[0]: for row in matrix: result.append(row.pop()) if matrix: result += matrix.pop()[::-1] if matrix and matrix[0]: for row in matrix[::-1]: result.append(row.pop(0)) return result # 示例调用 print(spiralOrder([[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]])) # 输出: [1,2,3,4,8,12,11,10,9,5,6,7]
算法分析
- 时间复杂度：(O(mn))，需要遍历矩阵中的每个元素一次。
- 空间复杂度：(O(1))，除输出数组外，额外使用的空间为常数。
方法三：递归剥离
解题步骤
- 递归剥离：递归地剥离矩阵的最外层，然后对剩下的矩阵递归调用同样的方法。
- 处理边界：每次递归调用前剥离顶部一行，并从四个边界收缩，然后旋转矩阵继续处理。
完整的规范代码
def spiralOrder(matrix): """ 递归剥离法按顺时针螺旋顺序返回矩阵中的所有元素 :param matrix: List[List[int]], 输入的矩阵 :return: List[int], 螺旋顺序的元素列表 """ return matrix and [*matrix.pop(0)] + spiralOrder([*zip(*matrix)][::-1]) # 示例调用 print(spiralOrder([[1, 2, 3], [4, 5, 6], [7, 8, 9]])) # 输出: [1,2,3,6,9,8,7,4,5]
算法分析
- 时间复杂度：(O(mn))，虽然每次递归都涉及到旋转和解压缩操作，但每个元素仅被处理一次。
- 空间复杂度：(O(m + n))，递归的深度由矩阵的尺寸决定，最坏情况下为 (min(m, n))。
方法四：迭代加标记
解题步骤
- 初始化标记：使用一个同样大小的矩阵来标记已访问的位置。
- 迭代遍历：按照螺旋的顺序遍历矩阵，使用方向数组来控制行走的方向（右、下、左、上）。
- 边界和标记检查：在遍历过程中，遇到边界或已访问标记时改变方向。
完整的规范代码
def spiralOrder(matrix): """ 迭代加标记法按顺时针螺旋顺序返回矩阵中的所有元素 :param matrix: List[List[int]], 输入的矩阵 :return: List[int], 螺旋顺序的元素列表 """ if not matrix: return [] rows, cols = len(matrix), len(matrix[0]) seen = [[False] * cols for _ in range(rows)] result = [] directions = [(0, 1), (1, 0), (0, -1), (-1, 0)] # right, down, left, up r = c = di = 0 # Start with the top-left corner going right for _ in range(rows * cols): result.append(matrix[r][c]) seen[r][c] = True nr, nc = r + directions[di][0], c + directions[di][1] if 0 <= nr < rows and 0 <= nc < cols and not seen[nr][nc]: r, c = nr, nc else: di = (di + 1) % 4 # Change direction r, c = r + directions[di][0], c + directions[di][1] return result # 示例调用 print(spiralOrder([[1, 2, 3], [4, 5, 6], [7, 8, 9]])) # 输出: [1,2,3,6,9,8,7,4,5]
算法分析
- 时间复杂度：(O(mn))，尽管涉及复杂的方向控制，但每个元素仅被访问一次。
- 空间复杂度：(O(mn))，需要额外的矩阵来标记访问过的元素。
不同算法的优劣势对比
| 特征 | 方法一: 模拟路径 | 方法二: 分层模拟 | 方法三: 递归剥离 | 方法四: 迭代加标记 |
| 时间复杂度 | (O(mn)) | (O(mn)) | (O(mn)) | (O(mn)) |
| 空间复杂度 | (O(1)) | (O(1)) | (O(m + n)) | (O(mn)) |
| 优势 | - 直观简单 | - 实现易于理解 | - 简洁的代码 | - 避免递归 |
| 劣势 | - 需要多个循环 | - 需要多次旋转矩阵 | - 高空间复杂度 | - 需要额外空间标记 |
应用示例 1: 图像处理
场景描述
在图像处理中，螺旋遍历可以用于实现各种图像变换效果，如螺旋形状的模糊、放大、缩小或像素重组。这种遍历方式可以帮助模拟自然现象中的螺旋图案，或在艺术处理中创造特定的视觉效果。
具体应用
- 螺旋模糊效果：
- 将图像从中心向外以螺旋的方式进行模糊处理，每一圈的模糊度逐渐增加，创造一种向外扩散的模糊视觉效果。
- 像素重组：
- 将图像的像素按照螺旋的顺序重新排列，形成一种全新的艺术效果。这种效果在设计领域尤其受欢迎，可用于海报设计、广告创意等。
实现示例
以螺旋模糊为例，下面是一段简化的Python代码，展示如何实现螺旋遍历并逐步增加模糊处理：使用任意一张图片即可进行实验
from PIL import Image, ImageFilter def spiralBlur(image_path): image = Image.open(image_path) pixels = image.load() width, height = image.size result = Image.new('RGB', (width, height)) result_pixels = result.load() directions = [(0, 1), (1, 0), (0, -1), (-1, 0)] # right, down, left, up x, y, di = 0, 0, 0 seen = set() for _ in range(width * height): result_pixels[x, y] = pixels[x, y] seen.add((x, y)) nx, ny = x + directions[di][0], y + directions[di][1] if (nx, ny) not in seen and 0 <= nx < width and 0 <= ny < height: x, y = nx, ny else: di = (di + 1) % 4 x, y = x + directions[di][0], y + directions[di][1] # Apply increasing blur local_radius = min(width, height) // 2 distance = ((x - width // 2)**2 + (y - height // 2)**2)**0.5 blur_radius = int((distance / local_radius) * 10) # Example blur increase small_region = image.crop((x-1, y-1, x+2, y+2)) blurred_region = small_region.filter(ImageFilter.GaussianBlur(radius=blur_radius)) result.paste(blurred_region, (x-1, y-1)) result.save('spiral_blurred_output.jpg') # Usage spiralBlur('path_to_image.jpg')
应用示例 2: 机器人路径规划
场景描述
在机器人路径规划中，尤其是在自动清扫机器人和搜索救援机器人的应用中，螺旋遍历可以系统地覆盖搜索区域。这种路径规划确保每一部分区域都能被访问，同时效率高于简单的来回扫描。
具体应用
- 自动清扫机器人：
- 设计路径使清扫机器人从一个房间的中心点开始，以螺旋的方式向外扩展，逐步清扫整个区域。这不仅确保清扫彻底，还能优化运行时间和电池使用效率。
- 搜索救援机器人：
- 在灾难响应中，
图像处理：
在图像处理中，螺旋遍历算法可以用于从中心向外逐层处理像素，用于特定的图像变换或视觉效果的生成。
机器人路径规划：
在机器人科技中，螺旋矩阵遍历可模拟机器人在二维空间的路径规划，特别是在需要系统地覆盖一个区域进行搜索或清扫时。救援机器人可能需要在废墟中搜索生还者。使用螺旋路径可以系统地覆盖搜寻区域，提高搜索效率和成功率。
实现示例
假设一个简单的基于网格的模型，下面是一段示例代码，表示如何规划路径：
def spiralPath(width, height): path = [] x, y = 0, 0 dx, dy = 0, 1 # Initial direction: move right while True: path.append((x, y)) if not (0 <= x + dx < width and 0 <= y + dy < height): dx, dy = dy, -dx # Change direction if (x + dx, y + dy) in path: break x, y = x + dx, y + dy return path # Usage example for a 5x5 area path = spiralPath(5, 5) print(path)
通过以上两个应用示例，我们可以看到螺旋矩阵遍历算法不仅理论上有趣，而且在实际应用中具有广泛的用途，特别是在需要系统覆盖和处理的场景中。
如果对你有帮助，给一个三连哦 谢谢大家！
欢迎关注微信公众号 数据分析螺丝钉
