一、题目
1、算法题目
“给定一个矩阵，按顺时针螺旋顺序，返回矩阵中的所有元素。”
题目链接：
来源：力扣（LeetCode）
链接：54. 螺旋矩阵 - 力扣（LeetCode） (leetcode-cn.com)
2、题目描述
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
网络异常，图片无法展示
|
示例 1： 输入： matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出： [1,2,3,6,9,8,7,4,5] 复制代码
示例 2： 输入： matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]] 输出： [1,2,3,4,8,12,11,10,9,5,6,7] 复制代码
二、解题
1、思路分析
这道题要模拟螺旋矩阵的路径，初始位置在左上角，初始方向是向右，当路径超出界限或进入之前访问的位置时，顺时针旋转，进入下一个方向。
所以，需要判断路径是否进入之前访问的位置，然后判断路径是否结束。
只要矩阵中的每个元素都被访问一次，矩阵中的元素数量就是路径的长度，路径的长度达到矩阵中元素数量时就将该路径返回。
2、代码实现
代码参考：
public class Solution { public IList<int> SpiralOrder(int[][] matrix) { List<int> res = new List<int>(); int r1 = 0, r2 = matrix.Length - 1; if(r2==-1) return res; int c1 = 0, c2 = matrix[0].Length - 1; while(r1<=r2 && c1<=c2) { for (int i = c1; i <= c2; i++) res.Add(matrix[r1][i]); for (int i = r1 + 1; i <=r2; i++) res.Add(matrix[i][c2]); if(r1<r2 && c1<c2) { for (int i = c2 - 1; i>= c1; i--) res.Add(matrix[r2][i]); for (int i = r2 - 1; i > r1; i--) res.Add(matrix[i][c1]); } r1++; r2--; c1++; c2--; } return res; } } 复制代码
网络异常，图片无法展示
|
3、时间复杂度
时间复杂度 ： O(mn)
其中 mm 和 nn 分别是输入矩阵的行数和列数。矩阵中的每个元素都要被访问一次。
空间复杂度： O(mn)
其中 mm 和 nn 分别是输入矩阵的行数和列数。矩阵中的每个元素都要被访问一次。
三、总结
这个解题方法，需要记录已经走过的路径，所以时间复杂度比较高。
还可以设定上下左右的边界，然后上下边界交错，说明遍历结束，跳出循环，得到答案。
这种方法执行用时和内存消耗都比较少，可以优化一下算法。
