当前位置: 开发笔记 > 编程语言 > 正文

螺旋矩阵c++语言_一起刷leetcode之螺旋矩阵（头条和美团真题）

作者：鱼儿什么都知道丶 | 来源：互联网 | 2023-10-10 15:58

微信公众号：每天晒白牙关注可了解更多编程知识。问题或建议，请公众号留言;如果你觉得文章对你有帮助，欢迎关注与转发题目描述给定一个包含m*n

微信公众号&＃xff1a;每天晒白牙
关注可了解更多编程知识。问题或建议&＃xff0c;请公众号留言;如果你觉得文章对你有帮助&＃xff0c;欢迎关注与转发

题目描述

给定一个包含 m*n 个元素的矩阵(m 行&＃xff0c;n 列)&＃xff0c;请按顺时针螺旋顺序&＃xff0c;返回矩阵中所有元素

leetcode 第 54 题
https://leetcode-cn.com/problems/spiral-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]

分析

方法 1 &＃xff1a;模拟遍历

通过示例&＃xff0c;我们可以很清晰的知道螺旋矩阵的遍历过程&＃xff0c;所以方法 1 中就采用模拟遍历的方法

首先&＃xff0c;我们需要定义行和列的方向数组&＃xff0c;因为当遍历到矩阵的边界需要换方向。同时遍历到已经遍历过的元素时也需要换方向&＃xff0c;不然就一直在最外层转圈了&＃xff0c;后面会解释

行的方向数组 int[] dr &＃61; {0, 1, 0, -1}

列的方向数组 int[] dc &＃61; {1, 0, -1, 0}

下面分别解释下

行方向向量	解释
0	往右遍历
1	往下遍历
0	往左遍历
-1	往上遍历

列方向向量	解释
1	往右遍历
0	往下遍历
-1	往左遍历
0	往上遍历

有了方向向量&＃xff0c;还需要有个二维数组记录已经遍历过的元素坐标 (row&＃xff0c;column) &＃xff0c;如果遍历过&＃xff0c;该坐标对应的值就是 true

boolean[][] seen &＃61; new boolean[row][column]

在做边界的判断的同时也要判断元素是否被访问过&＃xff0c;不然不然就一直在最外层转圈了。我们拿示例 1 举例子&＃xff0c;当遍历到元素 4 时&＃xff0c;如果此时不对已经遍历过的元素进行判断&＃xff0c;下一步就会遍历 1&＃xff0c;而不是 5&＃xff0c;如下图所示&＃xff1a;

对已经遍历过的元素进行判断

源码

public static List spiralOrder(int[][] matrix) { if (matrix.length &＃61;&＃61; 0) { return new ArrayList(); } int row &＃61; matrix.length; int column &＃61; matrix[0].length; List result &＃61; new ArrayList(row * column); // 方向数组 // 行方向 0&＃xff1a;右,1&＃xff1a;下,0&＃xff1a;左&＃xff0c;-1&＃xff1a;上 int[] dr &＃61; {0,1,0,-1}; // 列方向 1: 右&＃xff0c;0&＃xff1a;下&＃xff0c;-1&＃xff1a;左&＃xff0c;0&＃xff1a;上 int[] dc &＃61; {1,0,-1,0}; int r &＃61; 0, c &＃61; 0, di &＃61; 0; // 标记第 r 行 c 列的单元素被访问过了 boolean[][] seen &＃61; new boolean[row][column]; // 遍历整个二维数组即矩阵 for (int i &＃61; 0; i // 将下标对应的元素放到结果集中 result.add(matrix[r][c]); // 标记 r 行 c 列的元素被访问过了&＃xff0c;这个判断主要用在要换圈的时候&＃xff0c;因为如果没有这个限制&＃xff0c;它就不会缩小圈 seen[r][c] &＃61; true; // 下一步移动的候选位置 int nr &＃61; r &＃43; dr[di]; int nc &＃61; c &＃43; dc[di]; // 做边界与是否已经访问过的判断 if (nr >&＃61; 0 && nr &＃61; 0 && nc r &＃61; nr; c &＃61; nc; } else { // 说明到了边界了&＃xff0c;需要换方向了 di &＃61; (di &＃43; 1) % 4; r &＃61; r &＃43; dr[di]; c &＃61; c &＃43; dc[di]; } } return result; }

执行结果

方法1执行结果

复杂度分析

时间复杂度&＃xff1a;O(n)&＃xff0c;需要遍历矩阵中所有的元素

空间复杂度&＃xff1a;O(n)&＃xff0c;需要用到数组 seen 和 result

方法 2&＃xff1a;按层(圈)遍历

我们把这个矩阵像剥洋葱似的一层一层的剥开&＃xff0c;从最外层一直到最里层&＃xff0c;我们通过示例图看下流程

方法2流程分析

这个方法理解起来比较简单&＃xff0c;值得需要注意的一点是对当前层是否有 4 条边的判断即 rowMin

源码

public static List spiralOrder3(int[][] matrix) { if (matrix.length &＃61;&＃61; 0) { return new ArrayList(); } // rowMin 表示当前层行的最小下标 rowMax 表示当前层行的最大下标 int rowMin &＃61; 0, rowMax &＃61; matrix.length - 1; // columnMin 表示当前层列的最小下标 columnMax 表示当前层列的最大下标 int columnMin &＃61; 0, columnMax &＃61; matrix[0].length - 1; // (rowMin,columnMin) 代表当前层的左上角的坐标 (rowMax,columnMax) 表示当前层右下角的坐标 List result &＃61; new ArrayList(matrix.length * matrix[0].length); while (rowMin <&＃61; rowMax && columnMin <&＃61; columnMax) { // 遍历当前层的上面边的所有元素行坐标不变&＃xff0c;列坐标 column 从 columnMin 到 columnMax for (int column &＃61; columnMin; column <&＃61; columnMax; column&＃43;&＃43;) { result.add(matrix[rowMin][column]); } // 遍历当前层的右面边的所有元素列坐标不变&＃xff0c;行坐标 row 从 rowMin &＃43; 1 到 rowMax for (int row &＃61; rowMin &＃43; 1; row <&＃61; rowMax; row&＃43;&＃43;) { result.add(matrix[row][columnMax]); } // 如果当前层有 4 条边即满足条件 rowMin if (rowMin // 遍历当前层的下面边的所有元素行坐标不变&＃xff0c;列坐标从 columnMax -1 到 columnMinfor (int column &＃61; columnMax - 1; column >&＃61; columnMin; column--) { result.add(matrix[rowMax][column]); }// 遍历当前层左面边的所有元素列坐标不变&＃xff0c;行坐标从 rowMax -1 遍历到 rowMin &＃43; 1for (int row &＃61; rowMax - 1; row > rowMin; row--) { result.add(matrix[row][columnMin]); } }// 遍历一层后&＃xff0c;遍历下一层&＃xff0c;需要更新 rowMin、rowMax、columnMin、columnMax 的坐标 rowMin&＃43;&＃43;; rowMax--; columnMin&＃43;&＃43;; columnMax--; }return result; }