大家好,都吃晚饭了吗?我是Kaiqisan,是一个已经走出社恐的一般生徒,今天第一次更新算法题目,(注,本题来自左神算法)
题目
现有一个矩阵matrix,需要旋转输出其中的内容(如图)

上图的矩阵输出为 1 2 3 4 5 10 15 20 19 18 17 16 11 6 7 8 9 14 13 12
方法1
思路
设定一个左上角元素和右下角元素,以这两个元素为参考点,然后旋转遍历一圈之后,把这两个参考点往内缩,再旋转遍历一周
- 第一周遍历 遍历到第一列第二行后停止。
旋转打印矩阵java代码实现 - 左神算法基础课04 - Kaiqisan方法1方法2总结 - 第二周遍历 参考点变化
旋转打印矩阵java代码实现 - 左神算法基础课04 - Kaiqisan方法1方法2总结
所有点都遍历完成,遍历结束
代码实现(java)
// 转圈打印矩阵(顺时针)
package Alig2;
public class Demo04circlePrint {
public static void main(String[] args) {
int[][] matrix = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16}};
// 左上边界点的坐标
int left = 0;
int top = 0;
// 右下边界点的坐标
int right = matrix[0].length - 1;
int bottom = matrix.length - 1;
// 一遍迭代表循环输出打印了一周
while (left <= right && top <= bottom) {
doCirclePrint(matrix, left++, top++, right--, bottom--);
}
}
static void doCirclePrint(int[][] matrix, int left, int top, int right, int bottom) {
// 这里的意外情况出现在遍历到最内层之后两个边界点在行下标或列下标相等的情况
if (left == right && top != bottom) {
for (int i = top; i <= bottom; i++) {
System.out.println(matrix[i][right]);
}
return;
}
if (top == bottom && left != right) {
for (int i = left; i <= right; i++) {
System.out.println(matrix[top][i]);
}
return;
}
if (top == bottom && left == right) {
System.out.println(matrix[left][top]);
}
// 借助参考点旋转遍历
for (int i = left; i < right; i++) {
System.out.println(matrix[top][i]);
}
for (int i = top; i < bottom; i++) {
System.out.println(matrix[i][right]);
}
for (int i = right; i > left; i--) {
System.out.println(matrix[bottom][i]);
}
for (int i = bottom; i > top; i--) {
System.out.println(matrix[i][left]);
}
}
}
方法2
思路
魔方式旋转矩阵(前提,矩阵长宽相等)
一次旋转之后(就像是魔方被扭了一下一样)
还是需要利用参考点 A (left, top) B(right, bottom)
这个方法和上面的方法类似,只不过这次是遍历我们要让矩阵动,不要我们自己遍历的时候去移动
先输出一次矩阵内容,只输出从左上参考点A开始从左往右(对应上面矩阵是 1,2,3,不输出4是为了防止后面的输出重叠)
然后开始交换矩阵数据
如图箭头所示为交换矩阵内容的方向,
交换一次之后再次输出(如上第二张图片)
一个轮回完成四次,(第一个轮回输出为 1,2,3,4,8,12,16,15,14,13,9,5)四次完成之后,参考点移动,继续完成以上的操作,直到所有点都被遍历。
代码实现
package Alig2;
public class Demo04circlePrint {
public static void main(String[] args) {
int[][] matrix = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16}};
int left = 0;
int top = 0;
int right = matrix[0].length - 1;
int bottom = matrix.length - 1;
while (left <= right) {
doCirclePrint(matrix, left++, top++, right--, bottom--);
}
}
static void doSwap(int[][] matrix, int left, int top, int right, int bottom) {
int temp;
for (int i = 0; i < right - left; i++) {
// 元素交换
temp = matrix[left + i][top];
matrix[left + i][top] = matrix[left][bottom - i];
matrix[left][bottom - i] = matrix[right - i][bottom];
matrix[right - i][bottom] = matrix[right][top + i];
matrix[right][top + i] = temp;
}
}
static void doCirclePrint(int[][] matrix, int left, int top, int right, int bottom) {
// 旋转四次回来,为了还原数组
for (int i = 0; i < 4; i++) {
// 先打印输出,再旋转
for (int j = left; j < right; j++) {
System.out.println(matrix[top][j]);
}
doSwap(matrix, left, top, right, bottom);
}
}
}
总结
很重要的知识点,面试高频题,你还有什么理由不磨炼!上面给出两种方法,虽然复杂,但是它们的复杂度较低。