Leetcode-面试题29- 顺时针打印矩阵

题目描述

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

示例 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]

• 0 <= matrix.length <= 100
• 0 <= matrix[i].length <= 100

方法：边界模拟

根据题目示例 matrix = [[1,2,3],[4,5,6],[7,8,9]] 的对应输出 [1,2,3,6,9,8,7,4,5] 可以发现，顺时针打印矩阵的顺序是 “从左向右、从上向下、从右向左、从下向上” 循环。

• 在考虑设定矩阵的 “左 上 右 下” 四个边界，模拟矩阵的遍历顺序。

算法思想

1. 处理空值：当matrix 为空的时候，直接返回空列表[] 即可
2. 初始化：矩阵的四个边界 l r t b 用于打印结果列表 res
3. 循环打印： “从左到右 从上到下 从右到左 从下到上” 四个方法循环，每个方向打印做以下三件事情（各个方法具体信息见下表）
   • 根据边界打印，将元素添加到res的尾部
   • 边界向内收缩1（代表已被打印）
   • 判断是否打印完毕（边界是否相遇），若打印完毕则跳出。

4. 返回值：返回res 即可

打印方向	1. 根据边界打印	2. 边界向内收缩	3. 是否打印完毕
从左向右	左边界l ，右边界 r	上边界 t 加 1	是否 t > b
从上到下	上边界t , 下边界b	右边界 r 减 1	是否 l > r
从右到左	右边界r , 左边界l	下边界 b 减 1	是否 t > b
从下到上	下边界b , 上边界t	左边界 l 加 1	是否 l > r

class Solution {
    public int[] spiralOrder(int[][] matrix) {
        // 特判
        if(matrix.length == 0){
            return new int[0];
        }

        // 顺时针方向
        int l = 0;
        int r = matrix[0].length - 1;
        int t = 0;
        int b = matrix.length - 1;

        int index = 0;

        // 结果集
        int[] res = new int[(r + 1) * (b + 1)];


        while (true){
            // left to right
            for (int i = l; i <= r ; i++) {
                res[index] = matrix[t][i];
                index++;
            }
            // ++t ：先给t加1，然后用t的新值
            // t++ : 先用t的原值，然后t加1；
            if(++t > b) break;

            // top to bottom
            for (int i = t; i <= b ; i++) {
                res[index] = matrix[i][r];
                index++;
            }
            if(l > --r) break;

            // right to left
            for (int i = r; i >= l ; i--) {
                res[index] = matrix[b][i];
                index++;
            }
            if(t > --b) break;

            // bottom to top
            for (int i = b; i >= t ; i--) {
                res[index] = matrix[i][l];
                index++;
            }
            if(++l > r) break;
        }
        return res;
    }
}

Java 代码利用了 ++ 操作的便利性，详情可见 ++i 和 i++ 的区别 ；

res[x++] 等价于先给 res[x] 赋值，再给 x 自增 1；
++t > b 等价于先给 t 自增 1 ，再判断 t > b 逻辑表达式

复杂度分析：

• 时间复杂度 O(MN) ： M, N分别为矩阵行数和列数。
• 空间复杂度 O(1) ： 四个边界 l , r , t , b 使用常数大小的 额外 空间（ res 为必须使用的空间）。

打赏