输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
示例 1：
1
2
| 输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
|
示例 2：
1
2
| 输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]
|
限制：
0 <= matrix.length <= 1000 <= matrix[i].length <= 100
方法一：模拟
可以模拟打印矩阵的路径，初始位置是矩阵的左上角，初始方向是向右，当越界或者进入访问过的位置就顺时针旋转进入另一个方向。
判断是否访问过数组中的某一个元素需要一个 visited 数组，当元素被访问过时将其设置为 true。当路径的长度等于矩阵中元素数量时，结束循环。
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
27
28
29
30
31
| class Solution {
public int[] spiralOrder(int[][] matrix) {
if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
return new int[0];
}
int rows = matrix.length, cols = matrix[0].length;
boolean[][] visited = new boolean[rows][cols];
int total = rows * cols;
int[] order = new int[total];
int row = 0, col = 0;
int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int directionIndex = 0;
for(int i = 0; i < total; i++){
order[i] = matrix[row][col];
visited[row][col] = true;
int nextRow = row + directions[directionIndex][0], nextCol = col + directions[directionIndex][1];
if(nextRow < 0 || nextRow >= rows || nextCol < 0 || nextCol >= cols || visited[nextRow][nextCol]){
directionIndex = (directionIndex + 1) % 4;
}
row += directions[directionIndex][0];
col += directions[directionIndex][1];
}
return order;
}
}
|
时间复杂度 O(mn)，空间复杂度O(mn)。
方法二：按层模拟
可以将矩阵看成若干层，首先打印最外层的元素，其次打印次外层的元素，直到打印最内层的元素。
对于每层，从左上方开始以顺时针的顺序遍历所有元素。假设当前层的左上角位于(top, left)，右下角位于(bottom, right)，按照如下顺序遍历当前层的元素。
从左到右遍历上侧元素，依次为(top, left) 到 (top, right)
从上到下遍历右侧元素，依次为(top + 1, right) 到(bottom, right)。
如果 left < right 且 top < bottom ，则从右向左遍历下侧元素，依次为(bottom, right - 1) 到 (bottom, left + 1)，以及从下到上遍历左侧元素，依次为 (bottom, left) 到 (top + 1, left)。
遍历完当前层的元素之后，将 left 和 top 分别增加 1 ，将 right 和 bottom 分别减少 1，进入下一层遍历。
下图来自 Leetcode。
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
27
28
29
30
31
32
33
34
35
36
37
38
39
| class Solution {
public int[] spiralOrder(int[][] matrix) {
if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
return new int[0];
}
int rows = matrix.length, cols = matrix[0].length;
int[] order = new int[rows * cols];
int index = 0;
int left = 0, right = cols - 1, top = 0, bottom = rows - 1;
while(left <= right && top <= bottom){
for(int c = left; c <= right; c++){
order[index++] = matrix[top][c];
}
for(int r = top + 1; r <= bottom; r++){
order[index++] = matrix[r][right];
}
if(left < right && top < bottom){
for(int c = right - 1; c > left; c--){
order[index++] = matrix[bottom][c];
}
for(int r = bottom; r > top; r--){
order[index++] = matrix[r][left];
}
}
left++ ;
right-- ;
top++ ;
bottom-- ;
}
return order;
}
}
|
时间复杂度 O(mn)，空间复杂度O(1)。