给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
示例 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]
|
提示：
m == matrix.lengthn == matrix[i].length1 <= m, n <= 10-100 <= matrix[i][j] <= 100
方法一：模拟
我们可以确定箭头方向顺序为：向右、向下、向左、向上。使用一个数组来保存访问过的元素，在遍历过程中，如果遇到数组边界或已经访问过的元素，改变到下一个方向，继续访问。直到结果数组中的元素个数等于矩阵中元素个数。
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
|
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> order = new ArrayList<>();
if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
return order;
}
int rows = matrix.length, cols = matrix[0].length;
boolean[][] visited = new boolean[rows][cols];
int[][] directions = {{0, 1},{1, 0},{0, -1},{-1, 0}};
int total = rows * cols;
int directionIndex = 0;
int row = 0, col = 0;
for(int i = 0; i < total; i++){
order.add(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(n)，n 为矩阵中元素个数
- 空间复杂度O(n)
方法二：按层遍历
将矩阵看成若干层，依次输出每一层的元素。
对于一个矩阵，我们可以使用四个点来确定其范围，分别是左上角[top, left]，右上角[top, right]，左下角[bottom, left]，右下角[bottom, right]。
访问当前层的元素顺序分别为：
[top][left] … [top][right]
[top + 1][right] … [bottom][right]
[bottom][right - 1] … [bottom][left]
[bottom - 1][left] … [top + 1][left]
需要注意的是，当矩阵为一行元素（top == bottom）时，步骤1、3会造成元素重复访问;当矩阵为一列元素（left == right）时，步骤2、4 会造成元素重复访问。所以需要在访问步骤 3、4外面加上 top < bottom && left < right限制，来使这两个重复访问只执行一次。
要访问下一层元素，将 left 和 top 加一，right 和 bottom 减一即可。
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
| class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> order = new ArrayList<>();
if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
return order;
}
int rows = matrix.length, cols = matrix[0].length;
int left = 0, right = cols - 1, bottom = rows - 1, top = 0;
while(left <= right && top <= bottom){
for(int i = left; i <= right; i++){
order.add(matrix[top][i]);
}
for(int i = top + 1; i <= bottom; i++){
order.add(matrix[i][right]);
}
if(left < right && top < bottom){
for(int i = right - 1; i >= left; --i){
order.add(matrix[bottom][i]);
}
for(int i = bottom - 1; i >= top + 1; --i){
order.add(matrix[i][left]);
}
}
++top;
++left;
--right;
--bottom;
}
return order;
}
}
|
- 时间复杂度O(n)，n 为矩阵中元素个数
- 空间复杂度O(1)