题目描述
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下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.
解题思路一
public static ArrayList<Integer> printMatrix(int[][] matrix) {
if (matrix == null || matrix.length == 0)
return null; //无法构成矩阵
ArrayList<Integer> resultList = new ArrayList<Integer>();
int time = 1;//记录绕圈的次数
int rowLength = matrix.length;
int colLength = matrix[0].length;
while (colLength - time >= time - 1 && rowLength - time >= time - 1) {//仍可以绕圈
//先横向从左向右遍历
for (int i = time - 1; i <= colLength - time; i++) {
resultList.add(matrix[time - 1][i]);
}
//第二步，有效最后一列从上到下遍历
for (int i = time; i <= rowLength - time; i++) {
resultList.add(matrix[i][colLength - time]);
}
//第三步，有效最后一行从右向左遍历
for (int i = colLength - time - 1; i >= time - 1 && time - 1 != rowLength - time; i--) { // time - 1 != rowLength - time 避免重复输出当前行
resultList.add(matrix[rowLength - time][i]);
}
//第四步，有效最先一列，从下往上遍历
for (int i = rowLength - time - 1; i >= time && time - 1 != colLength - time; i--) { //time - 1 != colLength - time 避免输出重复列
resultList.add(matrix[i][time - 1]);
}
time++;
}
return resultList;
}
解题思路二
想象有四根线在切割，四根线的端点前后链接，确认每次转圈遍历的范围，每转一圈，向中间聚拢，其实跟思路一一致，思路一是以点作为对象考虑，而思路二是以线对对象考虑
public static ArrayList<Integer> printMatrix2(int[][] matrix) {
ArrayList<Integer> resultList = new ArrayList<Integer>();
if (matrix == null || matrix.length == 0) {
return resultList; //无法构成矩阵
}
int row = 0; //遍历的当前行坐标
int rowLength = matrix.length - 1;//行坐标上界
int col = 0; //遍历的当前列坐标
int colLength = matrix[0].length - 1; //列坐标上界
//想象有四根线在切割输出
while (row <= rowLength && col <= colLength) {//仍可以绕圈
// 一根线 0度正序输出（从左到右）
for (int i = col; i <= colLength; i++) {
resultList.add(matrix[row][i]);
}
//第二步，一根线90度正序输出（从上到下）
for (int i = row + 1; i <= rowLength; i++) {
resultList.add(matrix[i][colLength]);
}
//第三步，一根线180度逆序输出（从右到左）
for (int i = colLength - 1; i >= col && row != rowLength; i--) { // row != rowLength 避免重复逆序输出当前行
resultList.add(matrix[rowLength][i]);
}
//第四步，一根线270度逆序输出（从下到上）
for (int i = rowLength - 1; i >= row + 1 && col != colLength; i--) { //time - 1 != colLength - time 避免输出逆序重复列
resultList.add(matrix[i][col]);
}
//缩小四个点的范围
row++;
col++;
rowLength--;
colLength--;
}
return resultList;
}
解题思路三
类似于走迷宫，每次在一个方位走到尽头，然后循环切换下一个方位
public ArrayList<Integer> printMatrix4(int[][] matrix) {
ArrayList<Integer> resultList = new ArrayList<Integer>();
if (matrix == null || matrix.length == 0) {
return resultList; //无法构成矩阵
}
//四个方位的坐标变化
int[] dx = {0, 1, 0, -1};
int[] dy = {1, 0, -1, 0};
int x = 0; //当前行坐标
int y = 0; //当前列坐标
int rowLength = matrix.length - 1; //行坐标上界
int colLength = matrix[0].length - 1; //列坐标上界
int dir = 0; //初始行走方位
boolean[][] flag = new boolean[rowLength + 1][colLength + 1];//记录每个位置是否走过
while (x >= 0 && x <= rowLength && y >= 0 && y <= colLength && !flag[x][y]) {
resultList.add(matrix[x][y]);
flag[x][y] = true;//已走过
//把当前方位的格子全部走完
while (x + dx[dir] >= 0 && x + dx[dir] <= rowLength && y + dy[dir] >= 0 && y + dy[dir] <= colLength && !flag[x + dx[dir]][y + dy[dir]]) {
x += dx[dir]; //移动到一个方位
y += dy[dir];
resultList.add(matrix[x][y]);
flag[x][y] = true;
}
//当前方位走完，换下一方位
dir = (dir + 1) % 4;
x += dx[dir];
y += dy[dir];
}
return resultList;
}
