打印矩阵问题是这样一个问题：以顺时针或者逆时针的方式打印整个矩阵。因为这个打印的顺序和我们经常遍历矩阵的顺序完全不同，所以初次面对这个问题时，看似比较困难，但是仔细一想，解法又会非常多的，是一道不错的面试题（前提是以前没有做过）。

---

1.打印矩阵问题

这个问题来源于《剑指offer》中的面试题29，描述的是这样一个问题：

给你一个n*m的矩阵，请按照如下顺序打印矩阵：

例如，给出矩阵：

[
[1,2,3],
[4,5,6],
[7,8,9],
[10,11,12]
]
1
2
3
4
5
6

那么应该得到的打印顺序是：

[1,2,3,6,9,12,11,10,7,4,5,8]
1

2.问题分析

如果没做个这个问题，那么出其不意的点在于：这个矩阵打印的顺序和我们平时遍历矩阵的顺序不一样。
仔细一想问题出在哪里，我们平时遍历矩阵常见的做法是：一行一行的遍历或者一列一列的遍历，矩阵的一个下标先不变，另一个下标不断增加。

for(int i = 0; i < n; i++) {
	for(int j = 0; j < m; j++) {
		System.out.println(nums[i][j]);
	}
}
1
2
3
4
5

但是如果按照题目中这种方式打印，它的横坐标和纵坐标都得改变，所以我们不能简单的通过两个循环来解决这个问题了。

再深入的思考一下这个问题，其实这个问题本质是：将一个二维的矩阵一维化，我们需要找到一种二维坐标向一维坐标映射的关系，这种关系实质上也是一种满射关系。

理清问题的本质后，面对这种问题，我们通常的做法有两种：

• 1.多画几个矩阵，尝试找出这种映射关系。这种做法通常较难且具有不确定性。
• 2.通过代码模拟实际映射过程来间接找到这种映射关系。这种做法通常比较简单。

能直接通过第一种方法做出来说明在这个地方逻辑性很强，很善于发现规律。
大多数人应该会选择模拟的方式来解决这个问题，这里我们也采用模拟的方法去尝试解决这个问题。

我们将整个打印的过程回顾一下：从原点出发，一直向右走，走到末尾了，开始向下走，又走到末尾了，开始向左走，又走到末尾了，开始向上走，这个时候开始不是走到末尾了而是遇到已经走过的路了，然后继续向右走，依次类推。。。

这个过程是不是和走迷宫很像！就是一个人在一个二维矩阵中走路，我们规定一个初始方向（向右）和方向的顺序（右下左上），每当遇到边界或者遇到已经走过的点，就换一个方向接着走，直到把矩阵的每一个点都走到了。遇到边界很容易判断，如何判断是点是否已经走过？存起来即可，但是会产生一个O（n*m）的空间复杂度。
我们可以很轻松的借助一组方向向量去实现这个过程，具体代码如下：

    static int[] printMatrix(int[][] a) {
        if(a == null || a.length == 0 || a[0].length == 0) {
            return new int[0];
        }
        int r = a.length, c = a[0].length;
        boolean[][] visited = new boolean[r][c];
        int[] res = new int[r * c];
        int[][] d = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int dIndex = 0;
        int x = 0, y = 0;
        for(int i = 0; i < r * c; i++) {
            res[i] = a[x][y];
            visited[x][y] = true;
            int nextR = x + d[dIndex][0];
            int nextC = y + d[dIndex][1];
            if(nextR < 0 || nextR >= r || nextC < 0 || nextC >= c || visited[nextR][nextC]) {
                dIndex = (dIndex + 1) % 4;
            }
            x += d[dIndex][0];
            y += d[dIndex][1];

        }
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

这种解法具有较强的拓展性，拓展点在哪？你会发现，它遍历的顺序完全由一组方向向量已经转弯的条件控制，如果我换一种方向打印，只要稍微调整一下方向向量的顺序即可。

但是相应的，缺陷就在于多使用了一些空间，有没有办法不使用这些空间呢？那我们还是从这种接法出发，两个问题：

• 1.它使用的空间是否多余？
• 2.如果多余，怎么替代？

仔细想一下使用这些空间要解决的问题：判断一个点是否已经被访问过。但是在这种打印顺序下，真的需要把每个点是否被访问都存起来吗？很明显的看到，第一次遍历走完了最上面的一层，之后是不是只要遇到最上面的一层就能知道是否已经走过，那么我们可以将最上面一层一排的空间给优化成一个变量，代表着最上面访问过多少层了，同理，右边，下面，左边，是不是都可以用一个变量来代替，这样，我们通过四个变量，就解决了原先需要一个二维数组才能解决的问题。具体细节看代码：

static int[] printMatrix2(int[][] a) {
        if(a == null || a.length == 0 || a[0].length == 0) {
            return new int[0];
        }
        int r = a.length, c = a[0].length;
        int[] res = new int[r * c];
        int k = 0;
        int left = 0, right = c - 1, up = 0, below = r - 1;
        while(left <= right && up <= below) {
            for(int col = left; col <= right; col++) {
                res[k++] = a[up][col];
            }
            for(int row = up + 1; row <= below; row++) {
                res[k++] = a[row][right];
            }
            if(left < right && up < below) {
                for(int col = right - 1; col > left; col--) {
                    res[k++] = a[below][col];
                }
                for(int row = below; row > up; row--) {
                    res[k++] = a[row][left];
                }
            }
            left++;
            right--;
            up++;
            below--;
        }
        return res;
    }
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

这里重在找到两种思路的突破口，具体代码就不详细的分析了。

---

ATFWUS 2022-08-10