Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
Example
Given the following matrix:
1
2
3
4
5
| [
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
|
You should return [1,2,3,6,9,8,7,4,5].
Solution
(Spiral-Matrix.py) download
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
| class Solution(object):
def spiralOrder(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[int]
"""
if not matrix:
return []
left = 0
right = len(matrix[0])-1
top = 0
down = len(matrix)-1
direct = 0 # 0: go right, 1: go down, 2:go left, 3:go up
ret = []
while True:
if direct == 0:
for i in range(left,right+1):
ret.append(matrix[top][i])
top += 1
if direct == 1:
for i in range(top,down+1):
ret.append(matrix[i][right])
right -= 1
if direct == 2:
for i in range(right,left-1,-1):
ret.append(matrix[down][i])
down -= 1
if direct == 3:
for i in range(down,top-1,-1):
ret.append(matrix[i][left])
left += 1
if left > right or top > down:
return ret
direct = (direct+1)%4
|
(Spiral-Matrix.java) download
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
40
41
42
| public class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> ret = new LinkedList<Integer>();
if (matrix.length == 0) return ret;
int l = 0;
int r = matrix[0].length-1;
int u = 0;
int d = matrix.length-1;
// 方向
int[] direction = {0,1,2,3};
int i = 0;
while ((l<=r) && (u<=d)){
if (direction[i%4] == 0){
for (int j=l; j<=r;j++)
ret.add(matrix[u][j]);
u += 1;
}
else if (direction[i%4] == 1){
for (int j=u;j<=d;j++)
ret.add(matrix[j][r]);
r -= 1;
}
else if (direction[i%4] == 2){
for (int j=r; j>=l;j--)
ret.add(matrix[d][j]);
d -= 1;
}
else{
for (int j=d; j>=u;j--)
ret.add(matrix[j][l]);
l += 1;
}
i += 1;
}
return ret;
}
}
|