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

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

解题思路

本题的解题思路为：递归

递归方式如上图所示，我们将顺时针打印矩阵的思路转换为从外至里，一圈一圈打印的过程。

打印矩阵外圈的方法命名为 printOuter；

如果矩阵左上角顶点的坐标定义为（x1,y1），矩阵右下角顶点的坐标定义为（x2,y2），那么我们打印矩阵外圈的顺序应该为：

1. print (x1,y1) -> (x1,y2 - 1)

2. print (x1,y2) -> (x2 - 1,y2)

3. print (x2,y2) -> (x2,y1 + 1)

4. print (x2,y1) -> (x1 + 1,y1)

打印外圈之后，开始打印的矩阵左上角和右下角的坐标应变为：(x1 + 1,y1 + 1) 和 (x2 - 1,y2 - 1)；在满足 x1 与 x2相等，或 y1 与 y2 相等时，递归条件中止。

打印至最内圈时，也就是递归中止时，打印的矩阵或变为竖形条状，或变为横形条状（如果只有一个元素，处理的方式和竖形条状与横形条状任意一种的处理方式相同），这两种情况我们需要单独拿出来考虑。

代码

class Solution {
    public int[] spiralOrder(int[][] matrix) {
        if(matrix.length == 0 || matrix[0].length == 0){
            return new int[0];
        }
        int startX = 0;
        int startY = 0;
        int endX = matrix.length - 1;
        int endY = matrix[0].length - 1;
        List<Integer> res = new ArrayList<>();
        while(startX <= endX && startY <= endY){
            printOuter(matrix,res,startX++,startY++,endX--,endY--);
        }
        return res.stream().mapToInt(Integer::valueOf).toArray();
    }
    private void printOuter(int[][] matrix,List<Integer> res,int startX,int startY,int endX,int endY){
        int x = startX;
        int y = startY;
        if(startX == endX){
            while(y <= endY){
                res.add(matrix[x][y++]);
            }
            return;
        }else if(startY == endY){
            while(x <= endX){
                res.add(matrix[x++][y]);
            }
            return;
        }else{
            while(y < endY){
                res.add(matrix[x][y++]);
            }
            while(x < endX){
                res.add(matrix[x++][y]);
            }
            while(y > startY){
                res.add(matrix[x][y--]);
            }
            while(x > startX){
                res.add(matrix[x--][y]);
            }
            return;
        }
    }
}

复杂度分析

• 时间复杂度：O(MN)

M,N 分别为矩阵的行数和列数

• 空间复杂度：O(1)

虽然，我们使用了递归的概念，但是本题并没有真正占用方法栈的空间，我们只需要存储矩阵左上角以及右下角四个变量表示的两点坐标即可，所以空间复杂度为：O(1)