按层模拟
解题思路
解题思路同 leetcode🧑💻 54. 螺旋矩阵；
可以将矩阵看成若干层，首先输出最外层的元素，其次输出次外层的元素，直到输出最内层的元素；
对于每层，从左上方开始以顺时针的顺序遍历所有元素：
- 从左到右遍历 上 侧元素；
- 从上到下遍历 右 侧元素；
- 从右到左遍历 下 侧元素；
- 从下到上遍历 左 侧元素；
向内收缩的过程，如果 上下边界、左右边界 出现了碰撞，说明已经没有内层矩阵需要打印了，停止打印即可；
图解
复杂度
-
时间复杂度：
O(n^2)，其中 n 是给定的正整数，矩阵的大小是 n×n ，需要填入矩阵中的每个元素； -
空间复杂度：
O(1)，除了返回的矩阵以外，空间复杂度是常数。
代码实现
function generateMatrix(n: number): number[][] {
const res = new Array(n).fill(0).map(it => new Array(n).fill(0));
let left = 0, top = 0, right = n - 1, bottom = n - 1;
let inx = 1;
while (true) {
// 从左向右打印，上边界向下收缩一层
for (let i = left; i <= right; i++) res[top][i] = inx++;
if (++top > bottom) break; // 碰撞检测
// 向上到下打印，右边界向左收缩一层
for (let i = top; i <= bottom; i++) res[i][right] = inx++;
if (--right < left) break; // 碰撞检测
// 从右向左打印，下边界向上收缩一层
for (let i = right; i >= left; i--) res[bottom][i] = inx++;
if (--bottom < top) break; // 碰撞检测
// 从下向上打印，左边界向右收缩一层
for (let i = bottom; i >= top; i--) res[i][left] = inx++;
if (++left > right) break; // 碰撞检测
}
return res;
};
参考资料
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 54. 螺旋矩阵
上一篇
评论
