剑指offer-19、顺时针打印矩阵

题⽬描述

输⼊⼀个矩阵，按照从外向⾥以顺时针的顺序依次打印出每⼀个数字，例如，如果输⼊如下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 （因为已经遍历完成上边界⼀⾏），判断上边界加上⼀之后是否⼤于下边界，如果是则调出。
之后执⾏类型操作，从上到下，从右到左，从下到上。

具体思路如下：

• 定义四个边界：上(up)、下(down)、左(left)、右(right)
  
• 按照顺时针方向遍历当前层：
  
  
  
  • 从左到右遍历上边界
    
  • 从上到下遍历右边界
    
  • 从右到左遍历下边界
    
  • 从下到上遍历左边界
    
  
  
• 遍历完一层后，收缩边界进入下一层
  

1. public class Solution {
2.     public ArrayList<Integer> printMatrix(int[][] matrix) {
3.         ArrayList<Integer> results = new ArrayList();
4.         
5.         if (matrix != null && matrix.length > 0) {
6.             int left = 0;
7.             int right = matrix[0].length - 1;
8.             int up = 0;
9.             int down = matrix.length - 1;
10.             int i;
11.             while (true) {
12.                 for (i = left; i <= right; i++) {
13.                     results.add(matrix[up][i]);
14.                 }
15.                 if ((++up) > down) {
16.                     break;
17.                 }
18.                 for (i = up; i <= down; i++) {
19.                     results.add(matrix[i][right]);
20.                 }
21.                 if (--right < left) {
22.                     break;
23.                 }
24.                 for(i=right;i>=left;i--){
25.                     results.add(matrix[down][i]);
26.                 }
27.                 if(--down<up){
28.                     break;
29.                 }
30.                 for(i=down;i>=up;i--){
31.                     results.add(matrix[i][left]);
32.                 }
33.                 if(++left>right){
34.                     break;
35.                 }
36.             }
37.         }
38.             return results;
39.     }
40. }

复制代码

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

• 时间复杂度​：O(mn)，每个元素被访问一次
  
• 空间复杂度​：O(1)，除了输出结果外只使用了固定数量的变量
  

方向模拟法

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

• 定义四个方向向量表示移动方向
  
• 使用一个二维数组记录已访问的位置
  
• 当遇到边界或已访问的位置时，顺时针旋转方向
  

1. public List<Integer> printMatrix(int[][] matrix) {
2.     List<Integer> result = new ArrayList<>();
3.     if (matrix == null || matrix.length == 0) return result;
4.    
5.     int rows = matrix.length, cols = matrix[0].length;
6.     boolean[][] visited = new boolean[rows][cols];
7.     int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
8.     int directionIndex = 0;
9.     int row = 0, col = 0;
10.    
11.     for (int i = 0; i < rows * cols; i++) {
12.         result.add(matrix[row][col]);
13.         visited[row][col] = true;
14.         
15.         int nextRow = row + directions[directionIndex][0];
16.         int nextCol = col + directions[directionIndex][1];
17.         
18.         if (nextRow < 0 || nextRow >= rows || nextCol < 0 || nextCol >= cols
19.             || visited[nextRow][nextCol]) {
20.             directionIndex = (directionIndex + 1) % 4;
21.         }
22.         
23.         row += directions[directionIndex][0];
24.         col += directions[directionIndex][1];
25.     }
26.     return result;
27. }

复制代码

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

递归分解法

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

• 遍历当前矩阵的最外层
  
• 将剩余部分作为新矩阵递归处理
  
• 递归终止条件：矩阵为空或只剩一行/一列
  

1. public List<Integer> printMatrix(int[][] matrix) {
2.     List<Integer> result = new ArrayList<>();
3.     if (matrix == null || matrix.length == 0) return result;
4.     spiralHelper(matrix, 0, matrix.length - 1, 0, matrix[0].length - 1, result);
5.     return result;
6. }
8. private void spiralHelper(int[][] matrix, int top, int bottom, int left, int right, List<Integer> result) {
9.     if (left > right || top > bottom) return;
10.    
11.     // 遍历上边
12.     for (int i = left; i <= right; i++) {
13.         result.add(matrix[top][i]);
14.     }
15.    
16.     // 遍历右边
17.     for (int i = top + 1; i <= bottom; i++) {
18.         result.add(matrix[i][right]);
19.     }
20.    
21.     if (top < bottom && left < right) { // 防止单行或单列
22.         // 遍历下边
23.         for (int i = right - 1; i >= left; i--) {
24.             result.add(matrix[bottom][i]);
25.         }
26.         
27.         // 遍历左边
28.         for (int i = bottom - 1; i > top; i--) {
29.             result.add(matrix[i][left]);
30.         }
31.     }
32.    
33.     // 递归处理内层
34.     spiralHelper(matrix, top + 1, bottom - 1, left + 1, right - 1, result);
35. }

复制代码

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

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！