题⽬描述

输⼊⼀个矩阵，按照从外向⾥以顺时针的顺序依次打印出每⼀个数字，例如，如果输⼊如下4 X 4 矩阵： 则依次打印出数字 1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10 .

思路及解答

边界收缩法（推荐）

我们使⽤的是不断缩⼩矩阵上，下，左，右四个边界的⽅法。⾸先定义⼀个up （上边界为0 ）, down (下边界为matrix.length - 1 )， left （左边界为0 ）， right （右边界为matrix[0].length - 1 ）。

从第⼀个⾏第⼀个开始打印，向左边界遍历到右边界，之后将上边界加上1 （因为已经遍历完成上边界⼀⾏），判断上边界加上⼀之后是否⼤于下边界，如果是则调出。

之后执⾏类型操作，从上到下，从右到左，从下到上。 具体思路如下：

  1. 定义四个边界：上(up)、下(down)、左(left)、右(right)

  2. 按照顺时针方向遍历当前层：

  • 从左到右遍历上边界

  • 从上到下遍历右边界

  • 从右到左遍历下边界

  • 从下到上遍历左边界

  1. 遍历完一层后，收缩边界进入下一层

注意： (++up) > down 代表 up=up+1;up>dowm 两个语句。

  • 时间复杂度​：O(mn)，每个元素被访问一次

  • 空间复杂度​：O(1)，除了输出结果外只使用了固定数量的变量

方向模拟法

模拟顺时针移动的路径，按照右→下→左→上的方向顺序遍历：

  1. 定义四个方向向量表示移动方向

  2. 使用一个二维数组记录已访问的位置

  3. 当遇到边界或已访问的位置时，顺时针旋转方向

  • 时间复杂度​：O(mn)

  • ​空间复杂度​：O(mn)，需要额外的visited数组

递归分解法

将矩阵分解为外层和内层，递归处理：

  1. 遍历当前矩阵的最外层

  2. 将剩余部分作为新矩阵递归处理

  3. 递归终止条件：矩阵为空或只剩一行/一列

  • 时间复杂度​：O(mn)

  • ​空间复杂度​：O(min(m,n))，递归栈的深度