wordpress nginx 500,湖南网站优化服务,阿里云的网站模版好吗,洛阳万悦网站建设文章目录 写在前面Tag题目来源题目解读解题思路方法一#xff1a;模拟方法二#xff1a;按层模拟 写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法#xff0c;两到三天更新一篇文章#xff0c;欢迎催更…… 专栏内容以分析题目为主#xff0c;并附带一些对于… 文章目录 写在前面Tag题目来源题目解读解题思路方法一模拟方法二按层模拟 写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法两到三天更新一篇文章欢迎催更…… 专栏内容以分析题目为主并附带一些对于本题涉及到的数据结构等内容进行回顾与总结文章结构大致如下部分内容会有增删 Tag介绍本题牵涉到的知识点、数据结构题目来源贴上题目的链接方便大家查找题目并完成练习题目解读复述题目确保自己真的理解题目意思并强调一些题目重点信息解题思路介绍一些解题思路每种解题思路包括思路讲解、实现代码以及复杂度分析知识回忆针对今天介绍的题目中的重点内容、数据结构进行回顾总结。 Tag
【矩阵】【数组】 题目来源
54. 螺旋矩阵 题目解读
从矩阵左上角 (0, 0) 位置开始按照顺时针旋转方向螺旋遍历依次输出矩阵的所有元素。 解题思路
方法一模拟
本题一个直观的思路就是按照要求进行模拟。按照 “向右-向下-向左-向上” 的顺序遍历矩阵读取每个位置的元素到答案数组中。
几个方向上的移动可以通过坐标加减来实现设当前位置坐标行号和列号为 (x, y)接下来是四个方向移动的坐标变换
向右x 不变y 1向下x 1y 不变向左x 不变y - 1向上x - 1y 不变
于是定义一个表示方向的二维数组 dirs[4][2] {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}注意第一维表示的方向要与 “向右-向下-向左-向上” 顺序一一对应。
我们还要使用一个数组 visited 来记录当前位置是否遍历过如果遍历过我们也要改变遍历的方向因为要求是螺旋遍历输出所有的元素。
当前的移动方向索引用 dirIdx 表示初始 dirIdx 0 表示向右移动。我们从 (0, 0) 位置出发
将读取到的位置 (row, col) 对应的元素存入答案数组更新数组 visited[row][col] 1更新下一个将要遍历的位置即 nrow row dirs[dirIdx][0]ncol col dirs[dirIdx][1]如果下一个遍历的位置超出了矩阵的边界或者是已经遍历过的位置那就要改变移动位置方向即改变 dirIdx更新下一个位置的真正方向如此遍历完所有位置即可得到最后的答案数组。
实现代码
class Solution {
public:vectorint spiralOrder(vectorvectorint matrix) {int m matrix.size(), n matrix[0].size();vectorint ret(m*n);const int dirs[4][2] {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};int dirIdx 0;int visited[m][n];memset(visited, 0, sizeof(visited));int i;int row 0, col 0;for(i 0; i m*n; i) {ret[i] matrix[row][col];visited[row][col] 1;int nrow row dirs[dirIdx][0];int ncol col dirs[dirIdx][1];if(nrow 0 || nrow m || ncol 0 || ncol n || visited[nrow][ncol]) {dirIdx (dirIdx 1) % 4; }row dirs[dirIdx][0];col dirs[dirIdx][1];}return ret;}
};复杂度分析
时间复杂度 O ( m n ) O(mn) O(mn) m m m 为矩阵 matrix 的行数 n n n 为列数。
空间复杂度 O ( 1 ) O(1) O(1)。
方法二按层模拟
可以将矩阵看成若干层我们一层一层的输出元素。我们定义第 k 层为距离最近边界距离为 k 的所有顶点。
对于每层我们从左上角开始以顺时针的顺序遍历所有元素。假设当前层的左上角为 (top, left)右下角为 (buttom, right)按照如下顺序进行遍历
从左到右遍历当前层的上部元素(top, left) 到 (top, right)从上到下遍历当前层的右部元素(top1, right) 到 (buttom, right)如果 left right 且 top buttom则从右到左遍历下部元素(buttom, right-1) 到 (buttom, left1)从下到上遍历左部元素(buttom, left) 到 (top1, left)。
遍历完当前层的所有元素之后更新层数为下一层将 lefttop--right--bottom。继续遍历直到遍历完所有元素为止。
实现代码
class Solution {
public:vectorint spiralOrder(vectorvectorint matrix) {if (matrix.size() 0 || matrix[0].size() 0) return {};int rows matrix.size(), columns matrix[0].size();vectorint res;int left 0, right columns - 1, top 0, bottom rows - 1; // 初始化为第一层while (left right top bottom) {for (int column left; column right; column) { // 更新上部res.push_back(matrix[top][column]);}for (int row top 1; row bottom; row) { // 更新右部res.push_back(matrix[row][right]);}if (left right top bottom) {for (int column right - 1; column left; --column) { // 更新下部res.push_back(matrix[bottom][column]);}for (int row bottom; row top; --row) { // 更新左部res.push_back(matrix[row][left]);}}// 更新到下一层left;right--;top;bottom--;}return res;}
};
复杂度分析
时间复杂度 O ( m n ) O(mn) O(mn) m m m 为矩阵 matrix 的行数 n n n 为列数。
空间复杂度 O ( 1 ) O(1) O(1)。 写在最后
如果文章内容有任何错误或者您对文章有任何疑问欢迎私信博主或者在评论区指出 。
如果大家有更优的时间、空间复杂度方法欢迎评论区交流。
最后感谢您的阅读如果感到有所收获的话可以给博主点一个 哦。
