This page looks best with JavaScript enabled

螺旋输出矩阵

 ·  ☕ 2 min read

问题

一个 m*n 的矩阵, 螺旋遍历输出每一项. 比如:

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

这个问题很久没做算法题, 然后思考了很久 🤦 才实现.

思考

一开始就想用遍历来输出,遍历的边界和起点,以及遍历的下标的 index 肯定要根据一些条件来动态调整.

观察输出 1 2 3 4 | 8 12 16 | 15 14 13 | 9 5 | 6 7 11 10 可以看到是:

  1. 先向右
  2. 再向下
  3. 再向左
  4. 再向上

然后 1~4 循环执行.

于是尝试先试着实现一次这样的循环(i: 行下标, j: 列下标), 那么条件就是:

条件 动作
i == 0 && j < n 向右 j++
i < m && j == n-1 向下 i++
i == m-1 && j > -1 向左 j--
i > 0 向上 i--

这样便能执行一圈输出. 通过观察可以看的最后向上执行完后会回到最开始的起点位置(例子中的1), 那为了让圈缩小, 于是可以在1 的前一个位置(例子中的 5) 时就改变遍历的边界条件, 让起点+1, 终点 -1.

实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * 按照螺旋方式输出矩阵
 * 比如:
 * 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
 */
public class PrintMatrix {

    public void print(final int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int count = m * n;
        int i = 0, j = 0;
        int maxI = m;
        int maxJ = n;
        int minI = 0;
        int minJ = 0;
        do {
            System.out.print(matrix[i][j] + " ");
            count--;
            if (j == minJ && i == minI + 1) {
                // 缩小圈子
                minJ++;
                minI++;
                maxI--;
                maxJ--;
            }
            if (i == minI && j < maxJ - 1) {
                j++;
            } else if (i < maxI - 1 && j == maxJ - 1) {
                i++;
            } else if (i == maxI - 1 && j > minJ) {
                j--;
            } else if (i > minI) {
                i--;
            }
        } while (count != 0);
    }
}

测试

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

    new PrintMatrix().print(mn);
}

Yang
WRITTEN BY
Yang
Developer