问题

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

1
2
3
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

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

思考

一开始就想用遍历来输出,遍历的边界和起点,以及遍历的下标的 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);
}