【LeetCode】剑指 Offer 29. 顺时针打印矩阵
一、设定边界
根据题目示例可以发现，顺时针打印矩阵的顺序是”从左向右，从上向下、从右向左、从下向上“循环
因此，考虑设定矩阵的”左、上、右、下“四个边界，模拟以上矩阵遍历顺序
算法流程：
- 空值处理：当 matrix 为空时，直接返回列表 [] 即可
- 初始化：矩阵左右上下四个边界 l、r、t、b，用于打印的结果列表 res
- 循环打印：”从左向右、从上向下、从右向左、从下向上“四个方向循环，每个方向打印中做以下三件事（各方向的具体信息见下表）；
- 根据边界打印，也就是将元素按顺序添加至列表 res 尾部
- 边界向内收缩 1 （代表已被打印）
- 判断是否打印完毕（边界是否相遇），若打印完毕则跳出
- 返回值：返回 res 即可
class Solution {
public int[] spiralOrder(int[][] matrix) {
if(matrix.length == 0) return new int[0];
int l = 0;
int r = matrix[0].length - 1;
int t = 0;
int b = matrix.length - 1;
int x = 0;
int[] arr = new int[(r+1)*(b+1)];
while(true) {
for(int i = l; i <= r; i++) arr[x++] = matrix[t][i];
if(++t > b) break;
for(int i = t; i <= b; i++) arr[x++] = matrix[i][r];
if(--r < l) break;
for(int i = r; i >= l; i--) arr[x++] = matrix[b][i];
if(--b < t) break;
for(int i = b; i >= t; i--) arr[x++] = matrix[i][l];
if(++l > r) break;
}
return arr;
}
}
- 时间复杂度 O(m*n)：M，N 分别为矩阵行数和列数
- 空间复杂度 P(1)：四个边界 l、r、t、b 使用常数大小的额外空间（res 为必须使用的空间）
二、按层模拟
可以将矩阵看成若干层，首先打印最外层的元素，其次打印次外层的元素，直到打印最内层的元素
定义矩阵的第 k 层是到最近边界距离为 k 的所有顶点。例如，下图矩阵最外层元素都是第 1 层，次外层元素都是第 2 层，剩下的元素都是第 3 层
[[1, 1, 1, 1, 1, 1, 1],
[1, 2, 2, 2, 2, 2, 1],
[1, 2, 3, 3, 3, 2, 1],
[1, 2, 2, 2, 2, 2, 1],
[1, 1, 1, 1, 1, 1, 1]]
对于每层，从左上方开始以顺时针的顺序遍历所有元素。假设当前层的左上角位于（top,left），右下角位于（bottom,right），按照如下顺序遍历当前层的元素
- 从左到右遍历上侧元素，依次为（top,left）到（top,right）
- 从上到下遍历右侧元素，依次为（top+1,right）到（bottom,right）
- 如果 left < right 且 top < bottom，则从右到左遍历下侧元素，依次为（bottom,right - 1）到（bottom,left + 1），以及从上到下遍历左侧元素，依次为（bottom,left）到（top + 1,left）
遍历完当前层的元素之后，将 left 和 top 分别增加 1，将 right 和 bottom 分别减少 1，进入下一层继续遍历，直到遍历完所有元素为止
class Solution {
public int[] spiralOrder(int[][] matrix) {
if(matrix.length == 0) return new int[0];
int rows = matrix.length;
int columns = matrix[0].length;
int[] arr = new int[columns * rows];
int l = 0;
int t = 0;
int r = columns - 1;
int b = rows - 1;
int x = 0;
while(l <= r && t <= b){
for(int i = l; i <= r; i++){
arr[x++] = matrix[t][i];
}
for(int i = t+1; i <= b; i++){
arr[x++] = matrix[i][r];
}
//如果 l = r，或者 t = b，那就不需要执行下面了，只需要进行下一次 while 循环就能遍历完
if(l < r && t < b){
for(int i = r - 1; i > l; i--){
arr[x++] = matrix[b][i];
}
for(int i = b; i > t; i--){
arr[x++] = matrix[i][l];
}
}
l++;
t++;
r--;
b--;
}
return arr;
}
}
- 时间复杂度：O(m * n)，其中 m 和 n 分别是输入矩阵的行数和列数。矩阵中的每个元素都要被访问一次
- 空间复杂度：O(1)，除了输出数组外，空间复杂度是常数