| # |
Title |
Difficulty |
Topic |
| 54 |
Spiral Matrix |
Medium |
Array |
Description
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
Example 1:
1
2
3
4
5
6
7
|
Input:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
Output: [1,2,3,6,9,8,7,4,5]
|
Example 2:
1
2
3
4
5
6
7
|
Input:
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]
]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]
|
Analyze
按顺序遍历，可以发现一次遍历包括4个步骤：
- 从左到右；
- 从上到下；
- 从右到左；
- 从下到上。
因此，大循环应该为遍历的几次，小循环为上述4个步骤。需要注意会发生重复遍历的地方，只有从右到左和从下到上可能会重复遍历。
Submission
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 {
public List<Integer> spiralOrder(int[][] matrix) {
if(matrix == null || matrix.length == 0 ||
matrix[0] == null || matrix[0].length == 0) return new ArrayList<>();
int m = matrix.length, n = matrix[0].length;
int loop = 0, maxLoop = (Math.min(m, n) % 2 == 0) ? Math.min(m, n) / 2 : Math.min(m, n) / 2 + 1;
List<Integer> res = new ArrayList<>(m*n);
while(loop < maxLoop) {
for(int j=loop; j<n-loop; j++)
res.add(matrix[loop][j]);
for(int i=loop+1; i<m-loop; i++)
res.add(matrix[i][n-loop-1]);
if(m - loop - 1 > loop) {
for(int j=n-loop-2; j>=loop; j--)
res.add(matrix[m-loop-1][j]);
}
if(loop < n - loop - 1) {
for(int i=m-loop-2; i>loop; i--)
res.add(matrix[i][loop]);
}
loop++;
}
return res;
}
}
|
Complex Analyze
时间复杂度为$O(m times n)$。
近期评论