题目描述
输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字。
样例
输入:
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]
]
输出:[1,2,3,4,8,12,11,10,9,5,6,7]
依次按$\Rightarrow$,$\Downarrow$,$\Leftarrow$,$\Uparrow$顺序遍历,每次切换方向时先判断可否访问。
时间复杂度 $O(mn)$,空间复杂度$O(1)$
C++ 代码
class Solution {
public:
vector<int> printMatrix(vector<vector<int> > matrix) {
vector<int> res;
if (matrix.empty() || matrix[0].empty()) return res;
int u = 0, d = matrix.size() - 1, l = 0, r = matrix[0].size() - 1;
while (1) {
for (int i = l; i <= r; ++i) res.push_back(matrix[u][i]); // 从左到右
if (++u > d) break; // 尝试往下
for (int i = u; i <= d; ++i) res.push_back(matrix[i][r]); // 从上到下
if (--r < l) break; // 尝试往左
for (int i = r; i >= l; --i) res.push_back(matrix[d][i]); // 从右到左
if (--d < u) break; // 尝试往上
for (int i = d; i >= u; --i) res.push_back(matrix[i][l]); // 从下到上
if (++l > r) break; // 尝试往右
}
return res;
}
};