输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下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 3 4 8 12 16 15 14 13 9 5 6 7 11 10
输入：
1 2 3 4
12 13 14 5
11 16 15 6
10 9 8 7
输出：1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
要求：额外的空间复杂度为O(1)
思路参考左程云，矩阵分圈处理方式。在矩阵中用左上角的坐标(startX, startY)和右下角的坐标(endX, endY)就可以表示一个子矩阵，比如例子中的矩阵，当(startX, startY)=(0, 0)时、(endX, endY)=(3, 3)时，表示的子矩阵就是整个矩阵，这个子矩阵的最外层如下：
1 2 3 4
5 8
9 12
13 14 15 16
如果能把这个子矩阵的外层转圈打印出来，那么就把startX, startY加1， 即(startX, startY) = (1, 1)， 再把endX, endY减1，即(endX, endY) = (2, 2)，此时表示子矩阵如下
6 7
10 11
将这个子矩阵转圈打印出来，接着把startX, startY加1， 即(startX, startY) = (2, 2)， 再把endX, endY减1，即(endX, endY) = (1, 1)，如果发现左上角坐标跑到了右下角坐标的右方或下方，整个过程就停止了。
AC的代码：
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printMatrix(int [][] matrix) {
if (matrix == null) return null;
int startX = 0, startY = 0;
int endX = matrix.length - 1, endY = matrix[0].length - 1;
ArrayList<Integer> list = new ArrayList<Integer>();
while (startX <= endX && startY <= endY) {
print(matrix, startX++, startY++, endX--, endY--, list);
}
return list;
}
private void print(int[][] matrix, int startX, int startY, int endX, int endY, ArrayList<Integer> list) {
if (startX == endX) { // 只有一行了
for (int i = startY; i <= endY; ++i) {
list.add(matrix[startX][i]);
}
} else if (startY == endY) { // 只有一列了
for (int i = startX; i <= endX; ++i) {
list.add(matrix[i][startY]);
}
} else {
int curX = startX, curY = startY;
while (curY != endY) {
list.add(matrix[startX][curY++]);
}
while (curX != endX) {
list.add(matrix[curX++][endY]);
}
while (curY != startY) {
list.add(matrix[endX][curY--]);
}
while (curX != startX) {
list.add(matrix[curX--][startY]);
}
}
}
}
==========================Talk is cheap, show me the code=======================
京公网安备 11010502036488号