剑指 Offer 29: 顺时针打印矩阵

[songyy5517]

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

示例 2：

输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]

[songyy5517]

思路：循环 & 按方向分情况讨论

1. 异常处理；
2. 定义相关变量（行列首尾指针）；
3. 循环打印矩阵：将顺时针打印操作分解为右，下，左，上，进行完每个操作之后更新指针/数组值，并进行范围判断；（2023/2/24）
   • 若指针越界，则跳出循环。
4. 返回数组；

复杂度分析：

• 时间复杂度： $O(MN)$ ， $M, N$ 分别为矩阵的行列数，需要打印矩阵中的所有元素；
• 空间复杂度： $O(1)$ ，额外定义了常数大小的变量（大小为 $MN$ 的数组res为必须使用的空间）。

[songyy5517]

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printMatrix(int [][] matrix) {
       // 思路：分类讨论（打印方向 & 打印范围）
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
            return new ArrayList();

        int row_start = 0, col_start = 0;
        int row_end = matrix.length;
        int col_end = matrix[0].length;

        ArrayList<Integer> res = new ArrayList();

        while (row_start <= row_end - 1 && col_start <= col_end - 1){
            // 向右打印
            for (int i = col_start; i < col_end; i++){
                res.add(matrix[row_start][i]);
            }

            if (++ row_start >= row_end)
                break;

            // 向下打印
            for (int i = row_start; i < row_end; i++)
                res.add(matrix[i][col_end - 1]);    // !col不能放在前面

            if (col_start >= --col_end)
                break; 

            // 向左打印
            for (int i = col_end - 1; i >= col_start; i--)
                res.add(matrix[row_end - 1][i]);

            if (row_start >= --row_end)
                break;

            // 向上打印
            for (int i = row_end - 1; i >= row_start; i--)
                res.add(matrix[i][col_start]);

            if (++col_start >= col_end)
                break; 
        }

        return res;

    }
}

[songyy5517]

2023/2/24：

1. 简化代码：每次打印操作完成，更新相应指针之后，需要马上对范围进行判断。若超出范围，则可直接跳出循环。
2. 边界条件需要仔细考虑（2023/2/25）

2023/10/4 2023/10/5