方形矩阵旋转（48）题解
题目
给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。
不占用额外内存空间能否做到？
示例 1:
给定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
原地旋转输入矩阵，使其变为:
[
[7,4,1],
[8,5,2],
[9,6,3]
]示例 2:
给定 matrix =
[
[ 5, 1, 9,11],
[ 2, 4, 8,10],
[13, 3, 6, 7],
[15,14,12,16]
],
原地旋转输入矩阵，使其变为:
[
[15,13, 2, 5],
[14, 3, 4, 1],
[12, 6, 8, 9],
[16, 7,10,11]
]分析
给出的矩阵形状是个N x N的正方形矩阵，所以他的宽高是已知的N，要求旋转90度，那横向排列的数组就变为了竖向排列，填充方式也要变成倒序填充。
如图：
在这里插入图片描述
转换完来看就是横向下标变为倒序的竖向下标了 ，算式： 横向index = 竖向N-1-index
代码
如果允许使用一个空矩阵接受就非常简单，时间复杂度：O(n²) 空间复杂度：O(2n)
public void rotate(int[][] matrix) {
int[][] result = new int[matrix.length][matrix.length];
for (int i = 0; i < matrix.length; i++) {
int now[] = matrix[i];
// 计算旋转后下标
int index = matrix.length-1-i;
for (int j = 0; j < now.length; j++) {
result[j][index] = now[j];
}
}
}题目还要求尝试不适应额外空间，所以就不能用临时矩阵，需要再给定的矩阵内旋转，也就是原地旋转；时间复杂度：O(n²) 空间复杂度：O(1)
在原地旋转的话会覆盖一部分值，所以也需要存储被覆盖的值，如果按上面的直接一行进行覆盖调整那产生的覆盖值太多 ，所以要一个一个值进行调整到正确的位置。从每行第一位开始调整。
在这里插入图片描述
代码如下：
public void rotate(int[][] matrix) {
int length = matrix.length;
for (int i = 0; i < matrix.length/2; i++) {
for (int j = i; j < matrix.length - (i + 1); j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[length - j-1][i];
matrix[length - j -1][i] = matrix[length-i-1][length-j-1];
matrix[length-i-1][length-j-1] = matrix[j][length-i-1];
matrix[j][length-i-1] = temp;
}
}
}还有一种方式，正方形旋转90° = 正方形水平反转 + 对角线反转；时间复杂度：O(n²) 空间复杂度：O(1)
在这里插入图片描述
代码如下：
public void rotate(int[][] matrix) {
int n = matrix.length;
// 水平翻转
for (int i = 0; i < n / 2; ++i) {
for (int j = 0; j < n; ++j) {
int temp = matrix[i][j];
matrix[i][j] = matrix[n - i - 1][j];
matrix[n - i - 1][j] = temp;
}
}
// 主对角线翻转
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-09-07，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录