模拟矩阵路径进行遍历
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
思路：
由于矩阵形状相当规则，所以模拟顺时针方向遍历并不困难。关键点在于，决定何时转向，以及转向哪个方向，还有最终在何时停止。
转向的时机：我们可以先判定当前前进方向上的下一个位置是否「可达」。首先需要维护一个同样大小的 visited[][] 矩阵，记录访问过的位置，若访问过，则「不可达」。另外，当下个位置发生数组越界时，同样不可达。这样我们只要在「不可达」时转向，「可达」时前进即可。
方向确定：为了使代码简单，不至于对4个方向都做一次判断，我们可以维护一个类似时钟指针一样顺时针旋转的向量数组 directions[][]，这个数组里存储4个方向上的方向向量，例如， {0,1} 表示当前前进方向是上方。每次需要转向时，指针前进一位并对 4（数组长度） 求余即可进入下个方向。
终止条件：我们可以计数输出的数字个数，当个数达到要求时停止。
时间复杂度：O(mn)
空间复杂度：O(mn)
实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution {
public int[] spiralOrder(int[][] matrix) {
int height = matrix.length;
int width = height == 0 ? 0 : matrix[0].length;
int len = height * width;
int[] ans = new int[len];
boolean[][] visited = new boolean[height][width];
int[][] dirGroup = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int direction = 0;
int top = 0, bottom = height - 1, left = 0, right = width - 1;
int row = 0, col = 0;
for (int i = 0; i < len; i++) {
ans[i] = matrix[row][col];
visited[row][col] = true;
int nextRow = row + dirGroup[direction][0], nextCol = col + dirGroup[direction][1];
if (nextRow >= height || nextCol >= width || nextRow < 0 || nextCol < 0 || visited[nextRow][nextCol]) {
direction = (direction + 1) % 4;
}
row += dirGroup[direction][0];
col += dirGroup[direction][1];
}
return ans;
}
}
|
