【面试经典150 | 矩阵】螺旋矩阵

文章目录

写在前面
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 (mn)$ ， $m$ 为矩阵 matrix 的行数， $n$ 为列数。

空间复杂度： $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;}
};