【算法】顺时针打印矩阵

剑指 Offer 第 23 题-链表中环的入口结点

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

[[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]

数据范围:

0 <= matrix.length <= 100

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

例如：

方法 1

public class Jz29_2 {
   public static void main(String[] args) {
        final Jz29_3_1 jz = new Jz29_3_1();
        System.out.println(jz.printMatrix(new int[][]{
                {1, 2, 3, 1},
                {4, 5, 6, 1},
                {4, 5, 6, 1},
        }));

        System.out.println(jz.printMatrix(new int[][]{
                {1}, {2}, {3}, {4}, {5}
        }));

        System.out.println(jz.printMatrix(new int[][]{
                {1, 2, 3, 4, 5}
        }));

        System.out.println(jz.printMatrix(new int[][]{
                {1, 2, 3, 4},
                {5, 6, 7, 8},
                {9, 10, 11, 12},
                {13, 14, 15, 16}
        }));
    }

    /**
     * 对于只有一行或只有一列时，会重复
     */
    public ArrayList<Integer> printMatrix(int[][] matrix) {
        // 为空的情况
        if (matrix == null || matrix.length == 0) {
            return new ArrayList<>();
        }

        ArrayList<Integer> list = new ArrayList<>(matrix.length * matrix[0].length);
        int minX = 0;
        int maxX = matrix.length - 1;
        int minY = 0;
        int maxY = matrix[0].length - 1;

        int x, y;
        while (minX <= maxX && minY <= maxY) {
            // 用两个标识来判断本轮是否有下移或左移
            boolean down = false;
            boolean left = false;

            // 从左上角开始
            // 向右
            for (x = minX, y = minY; y <= maxY; y++) {
                list.add(matrix[x][y]);
            }

            // 向下
            for (x = minX + 1, y = maxY; x <= maxX; x++) {
                list.add(matrix[x][y]);
                down = true;
            }

            // 向左，左移之前确认是否有下移，防止重复
            for (x = maxX, y = maxY - 1; down && y >= minY; y--) {
                list.add(matrix[x][y]);
                left = true;
            }

            // 向上，上移之前确认是否有左移，防止重复
            for (x = maxX - 1, y = minY; left && x > minX; x--) {
                list.add(matrix[x][y]);
            }

            // 瘦身一圈
            minX++;
            maxX--;
            minY++;
            maxY--;
        }

        return list;
    }
}

方法 2

public class Jz29_4 {
    public static void main(String[] args) {
        final Jz29_4 jz = new Jz29_4();
        System.out.println(jz.printMatrix(new int[][]{
                {1, 2, 3, 1},
                {4, 5, 6, 1},
                {4, 5, 6, 1},
        }));

        System.out.println(jz.printMatrix(new int[][]{
                {1}, {2}, {3}, {4}, {5}
        }));

        System.out.println(jz.printMatrix(new int[][]{
                {1, 2, 3, 4, 5}
        }));

        System.out.println(jz.printMatrix(new int[][]{
                {1, 2, 3, 4},
                {5, 6, 7, 8},
                {9, 10, 11, 12},
                {13, 14, 15, 16}
        }));
    }

    /**
     * 起始点从左上角，沿对角线往中间靠
     */
    public ArrayList<Integer> printMatrix(int[][] matrix) {
        // 为空的情况
        if (matrix == null || matrix.length == 0) {
            return new ArrayList<>();
        }

        ArrayList<Integer> list = new ArrayList<>(matrix.length * matrix[0].length);
        int start = 0;
        while (matrix.length > start * 2 && matrix[0].length > start * 2) {
            addToList(list, matrix, start);
            start++;
        }

        return list;
    }

    private void addToList(ArrayList<Integer> list, int[][] matrix, int start) {

        // max row index
        int maxX = matrix.length - 1 - start;
        // max column index
        int maxY = matrix[0].length - 1 - start;

        boolean down = false;
        boolean left = false;

        // 从左向右
        for (int i = start; i <= maxY; ++i) {
            list.add(matrix[start][i]);
        }

        // 从上向下
        for (int i = start + 1; i <= maxX; i++) {
            list.add(matrix[i][maxY]);
            down = true;
        }

        // 从右向左
        for (int i = maxY - 1; down && i >= start; i--) {
            list.add(matrix[maxX][i]);
            left = true;
        }

        // 从下向上
        for (int i = maxX - 1; left && i > start + 1; i--) {
            list.add(matrix[i][start]);
        }

    }
}