物流手机网站模板,wordpress神秘礼盒插件,5g对网站建设的影响,自己想做个网站怎么做顺时针打印矩阵 输入一个矩阵#xff0c;按照从外向里以顺时针的顺序依次打印出每一个数字。
数据范围
矩阵中元素数量 [ 0 , 400 ] [0,400] [0,400]。
样例
输入#xff1a;
[[1, 2, 3, 4],[5, 6, 7, 8],[9,10,11,12]
]输出#xff1a;[1,2,3,4,8,12,11,10,9,5,6,7]算…顺时针打印矩阵 输入一个矩阵按照从外向里以顺时针的顺序依次打印出每一个数字。
数据范围
矩阵中元素数量 [ 0 , 400 ] [0,400] [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]算法思路
初始化 检查输入矩阵是否为空若为空则直接返回空结果。获取矩阵的行数 n 和列数 m。创建一个与矩阵大小相同的二维布尔数组 st用于标记已经访问过的元素。定义四个方向的位移数组 dx 和 dy分别表示上、右、下、左四个方向的移动。初始化当前位置 (x, y) 为 (0, 0)初始方向 d 为 1向右。 遍历矩阵 循环 n * m 次每次将当前元素加入结果数组并标记为已访问。计算下一个位置的坐标 (a, b)。如果下一个位置超出矩阵边界或已经被访问过则改变方向顺时针旋转 90 度。更新当前位置 (x, y) 为下一个合法位置。 返回结果 最终返回存储了螺旋顺序遍历结果的数组。
时间复杂度O(n * m)其中 n 是矩阵的行数m 是矩阵的列数。算法需要遍历矩阵中的每一个元素一次。空间复杂度O(n * m)用于存储访问标记的二维数组 st。如果忽略输出结果的空间额外空间复杂度为 O(n * m)。
class Solution {
public:vectorint printMatrix(vectorvectorint matrix) {vectorint res;if(matrix.empty()) return res;int n matrix.size(), m matrix[0].size();vectorvectorbool st(n, vectorbool(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;}
};
