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

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

难度简单160 收藏 分享 切换为英文 接收动态 反馈

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

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

解法一：寻找规律，按照题目要求一个个往里加：

public static int[] spiralOrder(int[][] matrix) {
        if(matrix==null||matrix.length==0||matrix[0].length==0){
            return new int[0];
        }
        int size=matrix.length*matrix[0].length;
        int[] result=new int[size];
        int row = matrix.length;
        int column = matrix[0].length;
        int loopSize=Math.min(row,column)/2+1;
        int currentIndex = 0;
        for (int i = 0; i < loopSize; i++) {
            //top_left->top_right
            int[] topMatrix = matrix[i];
            for (int j = i; j <column-i ; j++) {
                System.out.println(">>> topMatrix " + topMatrix[j]);
                result[currentIndex++] = topMatrix[j];
            }
            if (currentIndex == size) {
                return result;
            }
            //top_right->bottom_right
            int rightIndex = column - i - 1;
            for (int j = i+1; j < row-i-1; j++) {
                int[] middleMatrix = matrix[j];
                System.out.println(">>> middleMatrix " + middleMatrix[rightIndex]);
                result[currentIndex++] = middleMatrix[rightIndex];
            }
            //bottom_right->bottom_left
            if (currentIndex == size) {
                return result;
            }
            int[] bottomMatrix = matrix[row - i - 1];
            for (int j = column-i-1; j >=i ; j--) {
                System.out.println(">>> bottomMatrix " + bottomMatrix[j]);
                result[currentIndex++] = bottomMatrix[j];
            }
            if (currentIndex == size) {
                return result;
            }
            //bottom_left->top_left
            int leftIndex = i;
            for (int j = row-i-2; j >=i+1 ; j--) {
                int[] middleMatrix = matrix[j];
                System.out.println(">>> left middleMatrix " + middleMatrix[leftIndex]);
                result[currentIndex++] = middleMatrix[leftIndex];
            }
            if (currentIndex == size) {
                return result;
            }
        }

        return result;
    }

解法二：官方解法：

public static int[] spiralOrder(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return new int[0];
        }
        int rows = matrix.length, columns = matrix[0].length;
        boolean[][] visited = new boolean[rows][columns];
        int total = rows * columns;
        int[] order = new int[total];
        int row = 0, column = 0;
        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int directionIndex = 0;
        for (int i = 0; i < total; i++) {
            order[i] = matrix[row][column];
            visited[row][column] = true;
            int nextRow = row + directions[directionIndex][0], nextColumn = column + directions[directionIndex][1];
            if (nextRow < 0 || nextRow >= rows || nextColumn < 0 || nextColumn >= columns || visited[nextRow][nextColumn]) {
                directionIndex = (directionIndex + 1) % 4;
            }
            row += directions[directionIndex][0];
            column += directions[directionIndex][1];
        }
        return order;
    }

其实两个解法的思想都是控制边界以及转换方向。