9、剑指 Offer 29. 顺时针打印矩阵
目录
一、题目
剑指 Offer 29. 顺时针打印矩阵 难度简单
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
示例 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]
限制：
0 <= matrix.length <= 1000 <= matrix[i].length <= 100
注意：本题与主站 54 题相同：https://leetcode-cn.com/problems/spiral-matrix/
二、解法
2.1、四相边界法
核心思想：
已知顺时针打印矩阵的顺序是 “从左向右、从上向下、从右向左、从下向上” 循环，考虑设定矩阵的“左、上、右、下”四个边界，模拟以上矩阵遍历顺序。
- 上边界 ( top )、下边界 ( bottom )；
- 左边界 ( left )、右边界 ( right )；
| 打印方向 | 1. 根据边界打印 | 2. 边界向内收缩 | 3. 是否打印完毕 |
|---|---|---|---|
| 从左向右 | 左边界l ，右边界 r |
上边界 t 加 11 |
是否 t > b |
| 从上向下 | 上边界 t ，下边界b |
右边界 r 减 11 |
是否 l > r |
| 从右向左 | 右边界 r ，左边界l |
下边界 b 减 11 |
是否 t > b |
| 从下向上 | 下边界 b ，上边界t |
左边界 l 加 11 |
是否 l > r |
复杂度分析：
时间复杂度：O(MN)， M, N 分别为矩阵行数和列数。
空间复杂度：O(1)， 四个边界 l , r , t , b 使用常数大小的 额外 空间（ res 为必须使用的空间）。
代码：
class Solution {
public int[] spiralOrder(int[][] matrix) {
if (matrix.length == 0) return new int[0];
int l = 0, r = matrix[0].length - 1, t = 0, b = matrix.length - 1, x = 0;
int[] res = new int[(r + 1) * (b + 1)];
while (true) {
for (int i = l; i <= r; i++)
res[x++] = matrix[t][i]; // left to right.
if (++t > b) break;
for (int i = t; i <= b; i++)
res[x++] = matrix[i][r]; // top to bottom.
if (l > --r) break;
for (int i = r; i >= l; i--)
res[x++] = matrix[b][i]; // right to left.
if (t > --b) break;
for (int i = b; i >= t; i--)
res[x++] = matrix[i][l]; // bottom to top.
if (++l > r) break;
}
return res;
}
}
2.2、辅助矩阵法
核心思想：
可以模拟打印矩阵的路径。初始位置是矩阵的左上角，初始方向是向右，当路径超出界限或者进入之前访问过的位置时，顺时针旋转，进入下一个方向。
判断路径是否进入之前访问过的位置需要使用一个与输入矩阵大小相同的辅助矩阵 visited，其中的每个元素表示该位置是否被访问过。当一个元素被访问时，将 visited 中的对应位置的元素设为已访问。
如何判断路径是否结束？由于矩阵中的每个元素都被访问一次，因此路径的长度即为矩阵中的元素数量，当路径的长度达到矩阵中的元素数量时即为完整路径，将该路径返回。
复杂度分析：
时间复杂度：O(mn)，其中 m 和 n 分别是输入矩阵的行数和列数。矩阵中的每个元素都要被访问一次。
空间复杂度：O(mn)，需要创建一个大小为 m×n 的矩阵 visited 记录每个位置是否被访问过。
代码：
class Solution {
public int[] spiralOrder(int[][] matrix) {
// 边界条件
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return new int[0];
}
// 获取矩阵的行列数
int rows = matrix.length, columns = matrix[0].length;
// 构造辅助矩阵
boolean[][] visited = new boolean[rows][columns];
// 计算矩阵元素个数总和
int total = rows * columns;
// 答案
int[] result = new int[total];
// 当前坐标
int row = 0, column = 0;
// 方向
int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
// 当前是哪个方向
int directionIndex = 0;
for (int i = 0; i < total; i++) {
// 将当前元素写入 result
result[i] = matrix[row][column];
// 在辅助矩阵中标注已访问过
visited[row][column] = true;
// 计算当前方向的下一个坐标
int nextRow = row + directions[directionIndex][0], nextColumn = column + directions[directionIndex][1];
// 判断下一个坐标是否超限或已被访问过
if (nextRow < 0 || nextRow >= rows || nextColumn < 0 || nextColumn >= columns || visited[nextRow][nextColumn]) {
// 顺时针转向 90°
directionIndex = (directionIndex + 1) % 4;
}
// 按照当前方向，走一步
row += directions[directionIndex][0];
column += directions[directionIndex][1];
}
return result;
}
}