数组基操三连（2）
转圈打印矩阵
题目：
给定一个整型矩阵matrix，请按照转圈的方式打印它。例如：1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,打印结果为：1,2,3,4,5,12,16,15,14,13,9,5,6,7,11,10
要求：
额外空间复杂度为O（1）
思路：
矩阵分圈处理。在矩阵中用左上角的坐标（tR,tC）和右下角的坐标（dR,dC）就可以表示一个矩阵，比如，题目中的矩阵，当（tR,tC）=(0,0)，（dR,dC）=(3,3)时，表示的子矩阵就是整个矩阵，那么这个子矩阵的最外层的部分如下：
1 2 3 4
5 8
9 12
13 14 15 16
如果能把这个子矩阵的外层转圈打印出来，那么在(tR,tC)=(0,0)、(dR,dC)=(3,3)时，打印结果为：1,2,3,4,8,12,16,15,14,13,9,5。接下来令tR和tC加1，即(tR,tC)=(1,1)，令dR和dC减1，即(dR,dC)=(2,2)，此时表示的子矩阵如下：
6 7
10 11
再把这个子矩阵转圈打印出来，结果为：6,7,11,10。把tR和tC加1，即(tR,tC)=(2,2)，令dR和dC减1，即(dR,dC)=(1,1)。如果发现左上角坐标跑到右下角坐标的右方或下方，整个过程就停止。已经打印的所有结果连接起来就是我们要求的打印结果。
代码：
-
/**
-
* 转圈打印矩阵
-
*/
-
public class PrintMatrixSpiralOrder {
-
public void spiralOrderPrint(int[][] matrix) {
-
int tR = 0;
-
int tC = 0;
-
int dR = matrix.length - 1;
-
int dC = matrix[0].length - 1;
-
while (tR <= dR && tC <= dC) {
-
printEdge(matrix, tR++, tC++, dR--, dC--);
-
}
-
}
-
-
//转圈打印一个子矩阵的外层，左上角点（tR,tC），右下角点（dR,dC）
-
private void printEdge(int[][] matrix, int tR, int tC, int dR, int dC) {
-
if (tR == dR) {//子矩阵只有一行时
-
for (int i = tC; i <= dC; i++) {
-
System.out.print(matrix[tR][i] + " ");
-
}
-
} else if (tC == dC) {//子矩阵只有一列时
-
for (int i = tR; i <= dR; i++) {
-
System.out.print(matrix[i][tC] + " ");
-
}
-
} else {//一般情况
-
int curCol = tC;
-
int curRow = tR;
-
while (curCol != dC) {//从左向右
-
System.out.print(matrix[tR][curCol] + " ");
-
curCol++;
-
}
-
while (curRow != dR) {//从上到下
-
System.out.print(matrix[curRow][dC] + " ");
-
curRow++;
-
}
-
while (curCol != tC) {//从右到左
-
System.out.print(matrix[dR][curCol] + " ");
-
curCol--;
-
}
-
while (curRow != tR) {//从下到上
-
System.out.print(matrix[curRow][tC] + " ");
-
curRow--;
-
}
-
}
-
}
-
}
将正方形矩阵顺时针转动90°
题目：
给定一个N×N的矩阵matrix，把这个矩阵调整成顺时针转动90°后的形式。
例如：
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
顺时针转动90°后为：
13 9 5 1
14 10 6 2
15 11 7 3
16 12 8 4
要求：
额外空间复杂度为O(1).
思路：
仍然使用分圈处理的方式，
在矩阵中用左上角的坐标（tR,tC）和右下角的坐标（dR,dC）就可以表示一个矩阵，比如，题目中的矩阵，当（tR,tC）=(0,0)，（dR,dC）=(3,3)时，表示的子矩阵就是整个矩阵，那么这个子矩阵的最外层的部分如下：
1 2 3 4
5 8
9 12
13 14 15 16
在这个外圈中，1,4,16,13为一组，然后让1占据4的位置，4占据16的位置，16占据13的位置，13占据1的位置，一组就调整完了。然后2,8,15,9为一组，继续占据调整的过程，最后3,12,14,5为一组，继续占据调整的过程。然后(tR,tC)=(0,0)、(dR,dC)=(3,3)的子矩阵外层就调整完毕，接下来令tR和tC加1，即(tR,tC)=(1,1)，令dR和dC减1，即（dR,dC）=(2,2)，此时表示的子矩阵如下：
6 7
10 11
这个外层只有一组，就是6,7,11,10，占据调整之后即可。所以，如果子矩阵的大小是M×M，一共就有M-1组，分别进行占据调整即可。
代码：
-
/**
-
* 将正方形矩阵顺时针旋转90°
-
*/
-
public class RotateMatrix {
-
public static void rotate(int[][] matrix) {
-
int tR = 0;
-
int tC = 0;
-
int dR = matrix.length - 1;
-
int dC = matrix[0].length - 1;
-
while (tR < dR) {
-
rotateEdge(matrix, tR++, tC++, dR--, dC--);
-
}
-
}
-
-
private static void rotateEdge(int[][] matrix, int tR, int tC, int dR, int dC) {
-
int times = dC - tC;//times就是总的组数
-
int temp = 0;
-
for (int i = 0; i != times; i++) {//一次循环就是一组占据调整
-
temp = matrix[tR][tC + i];
-
matrix[tR][tC + i] = matrix[dR - i][tC];
-
matrix[dR - i][tC] = matrix[dR][dC - i];
-
matrix[dR][dC - i] = matrix[tR - i][dC];
-
matrix[tR - i][dC] = temp;
-
}
-
}
-
}
“之”字形打印矩阵
题目：
给定一个矩阵matrix，按照“之”字形的方式打印矩阵，例如：
1 2 3 4
5 6 7 8
9 10 11 12
“之”字形打印的结果为：1,2,5,9,6,3,4,7,10,11,8,12
要求：
额外空间复杂度为O（1）
思路;
上坐标（tR,tC）初始化为（0,0）,先沿着矩阵第一行移动（tC++），当到达第一行最右边的元素后，在沿着矩阵最后一列移动（tR++）。
下坐标（dR,dC）初始为（0,0）,先沿着矩阵第一列移动（dR++），当到达第一列最下边的元素时，再沿着矩阵最后一行移动（dC++）。
上坐标与下坐标同步移动，每次移动后的上坐标与下坐标的连线就是矩阵中的一条斜线，打印斜线上的元素即可。
如果上次斜线是从左下向右上打印的，这次一定是从右上向左下打印，反之亦然。总之，可以把打印的方向用boolean值表示，每次取反即可。
代码：
-
/**
-
* 之字形打印矩阵
-
*/
-
public class PrintMatrixZigZag {
-
public static void printMatrixZigZag(int[][] matrix) {
-
int tR = 0;
-
int tC = 0;
-
int dR = 0;
-
int dC = 0;
-
int endRow = matrix.length - 1;
-
int endCol = matrix[0].length - 1;
-
boolean fromUp = false;
-
while (tR != endRow + 1) {
-
printLevel(matrix, tR, tC, dR, dC, fromUp);
-
tR = tC == endCol ? tR + 1 : tR;
-
tC = tC == endCol ? tC : tC + 1;
-
dR = dR == endRow ? dR : dR + 1;
-
dC = dR == endRow ? dC + 1 : dC;
-
fromUp = !fromUp;
-
}
-
System.out.println();
-
}
-
-
private static void printLevel(int[][] matrix, int tR, int tC, int dR, int dC, boolean fromUp) {
-
if (fromUp) {
-
while (tR != dR + 1) {//从左下到右上
-
System.out.print(matrix[tR++][tC--] + " ");
-
}
-
} else {
-
while (dR != tR - 1) {//从右上到左下
-
System.out.print(matrix[dR--][dC++] + " ");
-
}
-
}
-
}
-
}
文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。
原文链接：fantianzuo.blog.csdn.net/article/details/83381130
- 点赞
- 收藏
- 关注作者
评论（0）