文章目录
- 写在前面
- Tag
- 题目来源
- 题目解读
- 解题思路
- 方法一:模拟
- 方法二:按层模拟
- 写在最后
写在前面
本专栏专注于分析与讲解【面试经典150】算法,两到三天更新一篇文章,欢迎催更……
专栏内容以分析题目为主,并附带一些对于本题涉及到的数据结构等内容进行回顾与总结,文章结构大致如下,部分内容会有增删:
- Tag:介绍本题牵涉到的知识点、数据结构;
- 题目来源:贴上题目的链接,方便大家查找题目并完成练习;
- 题目解读:复述题目(确保自己真的理解题目意思),并强调一些题目重点信息;
- 解题思路:介绍一些解题思路,每种解题思路包括思路讲解、实现代码以及复杂度分析;
- 知识回忆:针对今天介绍的题目中的重点内容、数据结构进行回顾总结。
Tag
【矩阵】【数组】
题目来源
54. 螺旋矩阵
题目解读
从矩阵左上角 (0, 0)
位置开始,按照顺时针旋转方向螺旋遍历依次输出矩阵的所有元素。
解题思路
方法一:模拟
本题一个直观的思路就是按照要求进行模拟。按照 “向右-向下-向左-向上” 的顺序遍历矩阵,读取每个位置的元素到答案数组中。
几个方向上的移动,可以通过坐标加减来实现,设当前位置坐标(行号和列号)为 (x, y)
,接下来是四个方向移动的坐标变换:
- 向右:
x
不变,y += 1
; - 向下:
x += 1
,y
不变; - 向左:
x
不变,y -= 1
; - 向上:
x -= 1
,y
不变;
于是,定义一个表示方向的二维数组 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:vector<int> spiralOrder(vector<vector<int>>& matrix) {int m = matrix.size(), n = matrix[0].size();vector<int> 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)
; - 从上到下遍历当前层的右部元素,
(top+1, right)
到(buttom, right)
; - 如果
left < right
且top < buttom
,则从右到左遍历下部元素,(buttom, right-1)
到(buttom, left+1)
;从下到上遍历左部元素,(buttom, left)
到(top+1, left)
。
遍历完当前层的所有元素之后,更新层数为下一层,将 ++left
,++top
,--right
,--bottom
。继续遍历,直到遍历完所有元素为止。
实现代码
class Solution {
public:vector<int> spiralOrder(vector<vector<int>>& matrix) {if (matrix.size() == 0 || matrix[0].size() == 0) return {};int rows = matrix.size(), columns = matrix[0].size();vector<int> 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)。
写在最后
如果文章内容有任何错误或者您对文章有任何疑问,欢迎私信博主或者在评论区指出 💬💬💬。
如果大家有更优的时间、空间复杂度方法,欢迎评论区交流。
最后,感谢您的阅读,如果感到有所收获的话可以给博主点一个 👍 哦。