题目描述
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
数据范围
矩阵中元素数量 [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]
方法一：模拟 O(n2)
我们可以模拟顺时针查找，遍历所有点并且按照一定方向一直探索，直到数组越界或该位置已经遍历过再改变方向。
我们拿题目样例进行举例，看看是怎么执行的：
第一趟遍历： [ 1 , 2 , 3 , 4 ] [1,2,3,4][1,2,3,4]
第二趟遍历： [ 1 , 2 , 3 , 4 , 8 , 12 ] [1,2,3,4,8,12][1,2,3,4,8,12]
第三趟遍历： [ 1 , 2 , 3 , 4 , 8 , 12 , 11 , 10 , 9 ] [1,2,3,4,8,12,11,10,9][1,2,3,4,8,12,11,10,9]
第四趟遍历： [ 1 , 2 , 3 , 4 , 8 , 12 , 11 , 10 , 9 , 5 ] [1,2,3,4,8,12,11,10,9,5][1,2,3,4,8,12,11,10,9,5]
第五趟遍历： [ 1 , 2 , 3 , 4 , 8 , 12 , 11 , 10 , 9 , 5 , 6 , 7 ] [1,2,3,4,8,12,11,10,9,5,6,7][1,2,3,4,8,12,11,10,9,5,6,7]
得到最终数组： [ 1 , 2 , 3 , 4 , 8 , 12 , 11 , 10 , 9 , 5 , 6 , 7 ] [1,2,3,4,8,12,11,10,9,5,6,7][1,2,3,4,8,12,11,10,9,5,6,7]
class Solution { public: vector<int> printMatrix(vector<vector<int> > matrix) { vector<int> ans; if (matrix.empty()) return ans; int n = matrix.size(), m = matrix[0].size(); int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 }; vector<vector<bool>> st(n, vector<bool>(m, false)); //状态数组 int x = 0, y = 0, d = 0; for (int i = 0; i < n * m; i++) { ans.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 ans; } };
欢迎大家在评论区交流~
