剑指offer-29-顺时针打印矩阵

快来打我* 2021-12-19 00:27 151阅读 0赞

题目：

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

1	2	3	4
    5	6	7	8
    9	10	11	12
    13	14	15	16

则依次打印出数字1、2、3、4、8、12、16、15、14、13、9、5、6、7、11、10。  
思路：  
![在这里插入图片描述][20190701205121153.png]  
思路  
　　每次打印矩阵最外面的一圈（用方法printMatrixInCircle()表示），每次都是这个操作，所以可以采用递归。每次打印矩阵的左上角的横纵坐标相同，即为start，而其余三个角的坐标都与行列数以及start有关，因此只需要for循环即可实现打印。

package offer;
    
    import java.util.ArrayList;
    import java.util.Arrays;
    
    /**
     * @author kankan
     * @creater 2019-06-30 20:42
     */
    //题目：输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
    
    public class PrintMatrix {
        public ArrayList<Integer> printMatrix(int[][] matrix) {
            if (matrix == null || matrix.length <= 0)
                return null;
            ArrayList<Integer> result = new ArrayList<>();
            printMatrixInCircle(matrix, 0, result);
            return result;
        }
    
        private void printMatrixInCircle(int[][] matrix, int start, ArrayList<Integer> result) {
            int row = matrix.length;//行
            int col = matrix[0].length;//列
            int endCol = col - 1 - start;//列的最大索引
            int endRow = row - 1 - start;//行的最大索引
            if (endCol < start || endRow < start)
                return;
            //仅一行
            if (endRow == start) {
                for (int i = start; i <= endCol; i++) {
                    System.out.print(matrix[start][i] + " ");
                    result.add(matrix[start][i]);
                }
                return;  //记得结束
            }
            //仅一列
            if (endCol == start) {
                for (int i = start; i <= endRow; i++) {
                    System.out.print(matrix[i][start] + " ");
                    result.add(matrix[i][start]);
                }
                return;  //记得结束
            }
    
            //打印边界
            //从左到右
            for (int i = start; i <= endCol; i++) {
                System.out.print(matrix[start][i] + " ");
                result.add(matrix[start][i]);
            }
            //从上到下
            for (int i = start + 1; i <= endRow; i++) {
                System.out.print(matrix[i][endCol] + " ");
                result.add(matrix[i][endCol]);
            }
            //从右到左
            for (int i = endCol - 1; i >= start; i--) {
                System.out.print(matrix[endRow][i] + " ");
                result.add(matrix[endRow][i]);
            }
            //从下到上
            for (int i = endRow - 1; i >= start + 1; i--) {
                System.out.print(matrix[i][start] + " ");
                result.add(matrix[i][start]);
            }
    
            //继续打印更内部的矩阵，令start+1
            printMatrixInCircle(matrix, start + 1, result);
        }
    
    
        public static void main(String[] args) {
            PrintMatrix demo = new PrintMatrix();
            int[][] a = {
       {1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16}};
    //      int[][] a= {};
    //      int[][] a= {
       {}};
    //      int[][] a= {
       {1}};
    //      int[][] a= {
       {1,2,3,4}};
    //      int[][] a= {
       {1},{2},{3},{4}};
    //      int[][] a= {
       {1,2,3},{4,5,6}};
    //      int[][] a=null;
            ArrayList<Integer> result = new ArrayList<>();
            result = demo.printMatrix(a);
            System.out.println(result);
        }
    }

![在这里插入图片描述][2019070120493995.png]  
剑指offer中提供的思路其实要更容易一些，首先分析循环结束的条件，打印第一圈左上角坐标为（0，0），第二圈左上角坐标为（1，1），以此类推每次循环的行列起始坐标都是相同的(start,start)。因此可以分析出循环继续的条件是columns > startX*2并且rows > startY*2。有了循环继续的条件后，我们要分析每次循环那4步的前提条件。第一步肯定是必定会经过的，因为打印一圈至少有一步。第二步的前提是终止行号大于起始行号，第三步的前提是终止行号大于起始行号，终止列号大于起始列号，因为圈内至少有2行2列，第四步的前提条件是终止行号比起始行号至少大2，终止列号大于起始行号，即至少有3行2列。代码如下：

package offer;
    
    import java.util.ArrayList;
    
    /**
     * @author kankan
     * @creater 2019-07-01 21:26
     */
    public class PrintMatrix2 {
        public ArrayList<Integer> printMatrix(int [][] matrix) {
            ArrayList<Integer> result = new ArrayList<>();
            if (0 == matrix.length){
                return result;
            }
            int rows = matrix.length;//行数
            int columns = matrix[0].length;//列数
            //循环继续的条件是columns > startX*2并且rows > startY*2
            int start = 0;
            while (rows > start * 2 && columns > start * 2){
                printOneCircle(matrix,start,result);
                start++;
            }
            return result;
        }
    
        private void printOneCircle(int[][] matrix, int start, ArrayList<Integer> result) {
            int endCol = matrix[0].length - 1 - start;//列
            int endRow = matrix.length - 1 - start;//行
            //从左往右
            //第一步,已经判断打印数组不为null，说明至少有一行
            for (int i = start; i <= endCol; i++) {
                System.out.print(matrix[start][i] + " ");
                result.add(matrix[start][i]);
            }
            //从上往下
            //第二步：终止行号大于起始行号
            if (start < endRow){
                for (int i = start + 1; i <= endRow; i++) {
                    System.out.print(matrix[i][endCol] + " ");
                    result.add(matrix[i][endCol]);
                }
            }
            //从右往左（判断是否会重复打印）
            //第三步：终止行号大于起始行号之外,要求终止列号大于起始列号之外
            if (start < endCol && start < endRow){
                for (int i = endCol - 1; i >= start; i--) {
                    System.out.print(matrix[endRow][i] + " ");
                    result.add(matrix[endRow][i]);
                }
            }
            // 从下往上（判断是否会重复打印）
            //第四步：终止行号比起始行号至少大于2,终止列号大于起始列号之外
            if (start < endCol && start < endRow - 1){
                for (int i = endRow - 1; i >= start + 1; i--) {
                    System.out.print(matrix[i][start] + " ");
                    result.add(matrix[i][start]);
                }
            }
        }
        public static void main(String[] args) {
            PrintMatrix demo = new PrintMatrix();
            int[][] a = {
       {1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16}};
    //      int[][] a= {};
    //      int[][] a= {
       {}};
    //      int[][] a= {
       {1}};
    //      int[][] a= {
       {1,2,3,4}};
    //      int[][] a= {
       {1},{2},{3},{4}};
            //int[][] a= {
       {1,2,3},{4,5,6}};
    //      int[][] a=null;
            ArrayList<Integer> result = new ArrayList<>();
            result = demo.printMatrix(a);
            System.out.println(result);
        }
    }

[20190701205121153.png]: /images/20211219/e0b5711dc69546988a008e0aff8f32f8.png
[2019070120493995.png]: /images/20211219/5083ad68861441ac911e55b30e6ea4d3.png