问题
一个 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~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);
}
|
