Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
Example 1:
Input:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
Output: [1,2,3,6,9,8,7,4,5]
Example 2:
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]
代码
Approach 1: Simulation
Complexity Analysis
Time Complexity: O(_N), where N_ is the total number of elements in the input matrix. We add every element in the matrix to our final answer.
Space Complexity: O_(_N), the information stored in seen and in ans.
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List ans = new ArrayList();
if (matrix.length == 0) return ans;
int R = matrix.length;
int C = matrix[0].length;
boolean[][] seen = new boolean[R][C];
int[] dr = {0, 1, 0, -1};
int[] dc = {1, 0, -1, 0}; // top, right, bottom, left
int r = 0, c = 0, di = 0;
for (int i = 0; i < R * C; i++) {
ans.add(matrix[r][c]);
seen[r][c] = true;
int cr = r + dr[di];
int cc = c + dc[di];
if (cr >= 0 && cr < R && cc >= 0 && cc < C && !seen[cr][cc]) {
r = cr;
c = cc;
} else {
di = (di + 1) % 4;
r += dr[di];
c += dc[di];
}
}
return ans;
}
}
Approach 2: Layer-by-Layer
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List ans = new ArrayList();
if (matrix.length == 0) return ans;
int r1 = 0, r2 = matrix.length - 1;
int c1 = 0, c2 = matrix.length[0] - 1;
while (r1 <= r2 && c1 <= c2) {
// top
for (int c = c1; c <= c2; c++) {
ans.add(matrix[r1][c]);
}
// right
for (int r = r1 + 1; r <= r2; r++) {
ans.add(matrix[r][c2]);
}
if (r1 < r2 && c1 < c2) { // 奇数最后一轮无法进行
// bottom
for (int c = c2 - 1; c > c1; c--) {
ans.add(matrix[r2][c]);
}
// left
for (int r = r2; r < r1; r--) {
ans.add(matrix[r][c1]);
}
}
r1++;
r2--;
c1++;
c2--;
}
return ans;
}
}