剑指offer26_顺时针打印矩阵

顺时针打印矩阵

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

数据范围

矩阵中元素数量 $[0,400]$。

样例

输入：[ [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. 初始化：
   • 检查输入矩阵是否为空，若为空则直接返回空结果。
   • 获取矩阵的行数 n 和列数 m。
   • 创建一个与矩阵大小相同的二维布尔数组 st，用于标记已经访问过的元素。
   • 定义四个方向的位移数组 dx 和 dy，分别表示上、右、下、左四个方向的移动。
   • 初始化当前位置 (x, y) 为 (0, 0)，初始方向 d 为 1（向右）。
2. 遍历矩阵：
   • 循环 n * m 次，每次将当前元素加入结果数组，并标记为已访问。
   • 计算下一个位置的坐标 (a, b)。
   • 如果下一个位置超出矩阵边界或已经被访问过，则改变方向（顺时针旋转 90 度）。
   • 更新当前位置 (x, y) 为下一个合法位置。
3. 返回结果：
   • 最终返回存储了螺旋顺序遍历结果的数组。

• 时间复杂度：O(n * m)，其中 n 是矩阵的行数，m 是矩阵的列数。算法需要遍历矩阵中的每一个元素一次。
• 空间复杂度：O(n * m)，用于存储访问标记的二维数组 st。如果忽略输出结果的空间，额外空间复杂度为 O(n * m)。

class Solution {public: vector<int> printMatrix(vector<vector<int> > matrix) { vector<int> res; if(matrix.empty()) return res; int n = matrix.size(), m = matrix[0].size(); vector<vector<bool>> st(n, vector<bool>(m)); int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; int x = 0, y = 0, d = 1; for(int k = 0; k < n * m; k ++) { res.push_back(matrix[x][y]); st[x][y] = true; int a = x + dx[d], b = y + dy[d]; if(a < 0 || a >= n || b < 0 || b >= m || st[a][b]) { d = (d + 1) % 4; a = x + dx[d], b = y + dy[d]; } x = a, y = b; } return res; }};