Spiral Matrix (M)
题目
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]
题意
将给定矩阵中的元素按照从外圈到内圈，顺时针螺旋输出。
思路
直接模拟从外到内的顺时针路径，输出每一个路径上的元素。从左上角顶点开始，初始方向向右，每次按照指定方向前进一个元素，如果下一个元素在矩阵外或已经在之前被访问过，则将前进方向顺时针转90°。重复上述操作，直到最后一次到达的位置在矩阵外或已经被访问过。
官方解答中还介绍了一种层遍历的方法：
{{uploading-image-675813.png(uploading...)}}
如图，每次遍历一层，将当前层中元素按照红色行从左到右、绿色列从上到下、蓝色行从右到左、紫色列从下到上的顺序添加到结果集中，完成后将上下左右四个边界各向内推进一层，重复操作。
代码实现
Java
模拟
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> ans = new ArrayList<>();
// 空矩阵处理
if (matrix.length == 0) {
return ans;
}
int m = matrix.length, n = matrix[0].length;
boolean[][] visited = new boolean[m][n]; // 记录已访问过元素
int[] iPlus = {0, 1, 0, -1};
int[] jPlus = {1, 0, -1, 0};
int direction = 0; // 下一次前进方向,0123分别为右下左上
int i = 0, j = 0; // 当前位置
for (int count = 0; count < m * n; count++) {
ans.add(matrix[i][j]);
visited[i][j] = true;
// 先判断以当前方向走到的下一个位置是否合法，不合法则转向
int nextI = i + iPlus[direction];
int nextJ = j + jPlus[direction];
if (nextI == -1 || nextJ == -1 || nextI == m || nextJ == n || visited[nextI][nextJ]) {
direction = (direction + 1) % 4;
i += iPlus[direction];
j += jPlus[direction];
} else {
i = nextI;
j = nextJ;
}
}
return ans;
}
}
层遍历
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> ans = new ArrayList<>();
if (matrix.length == 0) {
return ans;
}
int m = matrix.length, n = matrix[0].length;
// 四个参数确定四个边
int rowUp = 0, rowDown = m - 1;
int colLeft = 0, colRight = n - 1;
while (rowUp <= rowDown && colLeft <= colRight) {
for (int c = colLeft; c <= colRight; c++) {
ans.add(matrix[rowUp][c]);
}
for (int r = rowUp + 1; r <= rowDown; r++) {
ans.add(matrix[r][colRight]);
}
// 只有当前层不是一直线时，才有下边和左边
if (rowUp < rowDown && colLeft < colRight) {
for (int c = colRight - 1; c >= colLeft + 1; c--) {
ans.add(matrix[rowDown][c]);
}
for (int r = rowDown; r >= rowUp + 1; r--) {
ans.add(matrix[r][colLeft]);
}
}
// 向内缩小
rowUp++;
rowDown--;
colLeft++;
colRight--;
}
return ans;
}
}
JavaScript
模拟
/**
* @param {number[][]} matrix
* @return {number[]}
*/
var spiralOrder = function (matrix) {
if (matrix.length === 0) {
return []
}
let order = []
let m = matrix.length
let n = matrix[0].length
let stepI = [0, 1, 0, -1]
let stepJ = [1, 0, -1, 0]
let dir = 0
let visited = new Array(m).fill(0).map(v => new Array(n).fill(false))
let i = 0, j = 0
for (let cnt = 0; cnt < m * n; cnt++) {
order.push(matrix[i][j])
visited[i][j] = true
let nextI = i + stepI[dir]
let nextJ = j + stepJ[dir]
if (nextI === m || nextJ === n || nextJ === -1 || visited[nextI][nextJ]) {
dir = (dir + 1) % 4
nextI = i + stepI[dir]
nextJ = j + stepJ[dir]
}
i = nextI
j = nextJ
}
return order
}
层遍历
/**
* @param {number[][]} matrix
* @return {number[]}
*/
var spiralOrder = function (matrix) {
if (matrix.length === 0) {
return []
}
let order = []
let m = matrix.length
let n = matrix[0].length
let left = 0
let right = n - 1
let top = 0
let bottom = m - 1
while (top <= bottom && left <= right) {
for (let i = left; i <= right; i++) {
order.push(matrix[top][i])
}
for (let i = top + 1; i <= bottom; i++) {
order.push(matrix[i][right])
}
if (top < bottom && left < right) {
for (let i = right - 1; i > left; i--) {
order.push(matrix[bottom][i])
}
for (let i = bottom; i > top; i--) {
order.push(matrix[i][left])
}
}
top++
bottom--
left++
right--
}
return order
}