剑指Offer[浮云]问题19：顺时针打印矩阵

问题描述

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字， 例如，如果输入如下4 X 4矩阵：

则依次打印出数字 1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10。

解题思路

由于是按照从外到内的顺序依次打印，所以可以把矩阵想象成若干个圈，用一个循环来打印矩阵，每次打印矩阵中的一圈。假设矩阵的行数是row，列数是col，则每次都是从左上角开始遍历，而我们注意到左上角行标和列标总是相同的，假设是start，那么循环继续的条件就是row>start * 2 && col > start * 2。而对于每一圈的打印，遵循从左到右，从上到下，从右到左，从下到上的顺序。但是这里需要注意的是最后一圈的打印，由于矩阵并不一定是方阵，最后一圈有可能退化为只有一行，只有一列，甚至只有一个数，因此要注意进行判断，避免重复打印。

简而言之：

1. 第一步：从左到右打印一行
2. 第二步：从上到下打印一列
3. 第三步：从右到左打印一行
4. 第四步：从下到上打印一列

求解

这道题的解法其实可以理解为暴力求解，即按顺序遍历所有的数据即可，需要注意的是，循环中的边界值如何设定。

目前做过的题中，还没有遇到过 --right 、++left 这种先自增或自减然后执行操作的情况，所以虽然解题逻辑很清晰，但是代码编写的时候很费脑子，需要特别留意临界。

public static int[] spiralOrder(int[][] array){
        int[] result = new int[array.length * array[0].length];
        int index = 0;
        int top = 0, right = array[0].length - 1, bottom = array.length - 1, left = 0;
        while (true){
            for (int i = left; i <= right; i++){
                result[index++] = array[top][i];
            }
            if (++top > bottom) break;

            for (int i = top; i <= bottom; i++){
                result[index++] = array[i][right];
            }
            if (--right < left) break;

            for (int i = right; i >= left; i--){
                result[index++] = array[bottom][i];
            }
            if (--bottom < top) break;

            for (int i = bottom; i >= top; i--){
                result[index++] = array[i][left];
            }
            if (++left > right) break;
        }
        return result;
    }

完整代码

public static int[] spiralOrder(int[][] array){
        int[] result = new int[array.length * array[0].length];
        int index = 0;
        int top = 0, right = array[0].length - 1, bottom = array.length - 1, left = 0;
        while (true){
            for (int i = left; i <= right; i++){
                result[index++] = array[top][i];
            }
            if (++top > bottom) break;

            for (int i = top; i <= bottom; i++){
                result[index++] = array[i][right];
            }
            if (--right < left) break;

            for (int i = right; i >= left; i--){
                result[index++] = array[bottom][i];
            }
            if (--bottom < top) break;

            for (int i = bottom; i >= top; i--){
                result[index++] = array[i][left];
            }
            if (++left > right) break;
        }
        return result;
    }

    public static void main(String[] args) {
        int[][] array = new int[][]{
                {1, 2, 3, 4},
                {5, 6, 7, 8},
                {9, 10, 11, 12},
                {13, 14, 15, 16}};

        int[] result = spiralOrder(array);
        for (int i = 0; i < result.length; i++){
            System.out.print(result[i] + ", ");
        }
    }

结果展示