剑指Offer题解 - Day56
剑指 Offer 29. 顺时针打印矩阵
力扣题目链接[1]
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
「示例 1：」
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
「限制：」
0 <= matrix.length <= 1000 <= matrix[i].length <= 100
思路：
按照题目描述，我们需要顺时针打印矩阵中的每个数字。而顺时针打印遵循“从左向右、从上向下、从右向左、从下向上”的规律。
我们维护上右下左四个边界，每打印一边，就将边界往相反方向缩进一行。具体来说，
- 打印上边界所处行之后，将上边界向下缩进；
- 打印右边界所处列之后，将右边界向左缩进；
- 打印下边界所处行之后，将下边界向上缩进；
- 打印左边界所处列之后，将左边界向右缩进；
- 直到某一个边界越过了相对边界，则停止循环。
模拟
/**
* @param {number[][]} matrix
* @return {number[]}
*/
var spiralOrder = function(matrix) {
if(!matrix.length) return []; // 空矩阵返回空数组
let l = 0; // 初始化四边的边界
let r = matrix[0].length - 1;
let t = 0;
let b = matrix.length - 1;
let x = 0; // 初始化结果数组的索引
let res = []; // 初始化结果数组
while(true) {
for (let i = l; i <= r; i++) res[x++] = matrix[t][i];
if (++t > b) break;
for (let i = t; i <= b; i++) res[x++] = matrix[i][r];
if (l > --r) break;
for (let i = r; i >= l; i--) res[x++] = matrix[b][i];
if (t > --b) break;
for (let i = b; i >= t; i--) res[x++] = matrix[i][l];
if (++l > r) break;
}
return res;
};
- 时间复杂度 O(mn)。
- 空间复杂度 O(1)。
分析：
有几个点需要注意。初始化右边界和下边界的值，需要矩阵内层和外层的长度减一。给结果数组赋值的时候，通过x++达到了先赋值再索引加一的效果。
判断越界条件通过先自增或自减，再判断是否越界。就可以将边界缩进的同时判断越界情况。
最终返回结果数组即可。
总结
本题考查矩阵打印的模拟。难点在于边界情况的考虑与循环的终止。
复杂度方面，由于需要遍历矩阵所有的节点，因此时间复杂度是O(mn) 。声明变量占用常数级别的空间。
参考资料
[1]
力扣题目链接: https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/5vfh9g/
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2022-03-17，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
