矩阵_顺时针遍历

题目描述

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下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

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

分析

上述“顺时针”遍历举证存在规律：

1. 遍历过的行或列不再遍历，即可遍历范围在不断缩小。
2. 遍历的方向：右、下、左、上（循环）

使用4个变量存储可遍历范围的边界：

        columnLeft
            ↓
        
rowLeft→    1  →  2  →  3  →  4
                              ↓
            5  →  6  →  7     8
            ↑           ↓     ↓
            9     10  ← 11    12
            ↑                 ↓
rowRight→   13  ← 14  ← 15  ← 16
                  
                               ↑
                          columnRight

各方向遍历过程：

右：

int x = columnLeft;
while(y<=columnRight){
    [rowLeft][x];
    x++;
}
//此行作废（向下缩小可遍历范围）
rowleft++;

下：

int y = rowLeft;
while(y<=rowRight){
    [y][columnRight];
    y++;
}
//次列作废（向左缩小可遍历范围）
columnRight--;

左：

int x = columnRight;
while(x>=columnLeft){
    [rowRight][x];
    x--;
}
//次行作废（向上缩小可遍历范围）
rowRight++;

上：

int y = rowRight;
while(y<=rowLeft){
    [y][columnLeft];
    y--;
}
//次列作废（向右缩小范围）
columnLeft++;

Talk is cheap,show me the code!

public static ArrayList<Integer> printMatrix(int[][] matrix) {
    /**
     *           0  1  2  3  4  5
     *          ____________________
     * rL   0  [ 1  2  3  4  5  6  ]
     *      1  [ 7  8  9  10 11 12 ]
     * rR   2  [ 13 14 15 16 17 18 ]
     *           cL             cR
     */
    ArrayList<Integer> result = new ArrayList<>();
    int rowLeft = 0;
    int rowRight = matrix.length - 1;
    int columnLeft = 0;
    int columnRight = matrix[0].length - 1;
    while (true) {
        // 右 →
        for (int x = columnLeft; x <= columnRight; x++) {
            System.out.println(matrix[rowLeft][x]);
            result.add(matrix[rowLeft][x]);
        }
        rowLeft++;
        if (rowLeft > rowRight) {
            break;
        }

        // 下 ↓
        for (int y = rowLeft; y <= rowRight; y++) {
            System.out.println(matrix[y][columnRight]);
            result.add(matrix[y][columnRight]);
        }
        columnRight--;
        if (columnRight < columnLeft) {
            break;
        }

        // 左 ←
        for (int x = columnRight; x >= columnLeft; x--) {
            System.out.println(matrix[rowRight][x]);
            result.add(matrix[rowRight][x]);
        }
        rowRight--;
        if (rowRight < rowLeft) {
            break;
        }

        // 上 ↑
        for (int y = rowRight; y >= rowLeft; y--) {
            System.out.println(matrix[y][columnLeft]);
            result.add(matrix[y][columnLeft]);
        }
        columnLeft++;
        if (columnLeft > columnRight) {
            break;
        }
    }
    return result;
}