048.旋转图像
作者：沉默王二
发布时间：2024-09-18T16:45:40.916+0800
二哥瞎逼逼：9 月份对于准备秋招的球友来说，非常重要，但奇怪的是 9 月份的假期却很多，中秋过完马上就是国庆，就很容易刚提起劲然后就松懈下来，然后一眨眼就 10 月中旬了。国庆结束后，基本上 offer 就开奖了，也就意味着头部和肩部选手的秋招可以彻底告一个段落了。今天继续来一到 LeetCode 题，醒醒脑子。
题意
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
难度
中等
示例
示例 1：
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]
示例 2：
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
输入：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]]
### 分析 1
在我们上学的年级，经常出现一些找规律的题目，比如说 1,1,2,3,5,8,13,21 这样的数列，我们很容易找到这样一个规律，就是后一个数等于前两个数之和。
对于这道题，我们也可以找到这样一个规律：
第 i 行的元素旋转到了第 n-1-i 列；
第 j 列的元素旋转到了第 j 行。
一旦找到这个规律，题解就很容易了，我们只需要遍历一遍矩阵，然后将矩阵的元素旋转到对应的位置即可。
为了保证旋转的过程中有些元素不会被覆盖，我们可以对矩阵进行深拷贝。
题解如下：
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
class Solution04801 {
public void rotate(int[][] matrix) {
int n = matrix.length; // 获取矩阵的维度
int[][] matrix_new = new int[n][n]; // 创建一个新矩阵来保存原矩阵的副本
// 复制原矩阵的每一行到新的矩阵
for (int i = 0; i < n; i++) {
matrix_new[i] = Arrays.copyOf(matrix[i], n); // 复制每一行
}
// 旋转矩阵：将 matrix_new 中的元素重新放入 matrix 中
for (int i = 0; i < n; i++) { // 遍历原矩阵的每一行
for (int j = 0; j < n; j++) { // 遍历原矩阵的每一列
// 将 matrix_new[i][j] 旋转到 matrix[j][n - 1 - i]
matrix[j][n - 1 - i] = matrix_new[i][j];
}
}
}
public static void main(String[] args) {
Solution04801 solution = new Solution04801();
int[][] matrix = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
solution.rotate(matrix);
for (int[] row : matrix) {
for (int val : row) {
System.out.print(val + " ");
}
System.out.println();
}
// 输出:
// 7 4 1
// 8 5 2
// 9 6 3
}
}
来看一下题解效率：
很高，但是因为我们多了一个 matrix_new 的二维数组，所以在严格意义上并不符合原地旋转的要求。
分析 2
矩阵旋转 90 度，相当于把 A 挪到 B，B 挪到 C，C 挪到 D，D 挪到 A，这样的操作。
比如说一个 4x4 的矩阵，相当于是 2 层的同心圆，我们可以通过一层一层的旋转来完成整个矩阵的旋转。
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
class Solution04802 {
public void rotate(int[][] matrix) {
int n = matrix.length;
// 逐层旋转
for (int layer = 0; layer < n / 2; layer++) {
int first = layer; // 当前层的起始索引
int last = n - 1 - layer; // 当前层的结束索引
for (int i = first; i < last; i++) {
int offset = i - first; // 偏移量，用来计算位置
// 保存上边
int top = matrix[first][i];
// 左边 -> 上边
matrix[first][i] = matrix[last - offset][first];
// 下边 -> 左边
matrix[last - offset][first] = matrix[last][last - offset];
// 右边 -> 下边
matrix[last][last - offset] = matrix[i][last];
// 上边 -> 右边
matrix[i][last] = top;
}
}
}
public static void main(String[] args) {
Solution04802 solution = new Solution04802();
int[][] matrix = {
{ 1, 2, 3, 4},
{ 5, 6, 7, 8},
{ 9, 10, 11, 12},
{13, 14, 15, 16}
};
solution.rotate(matrix);
for (int[] row : matrix) {
for (int val : row) {
System.out.print(val + " ");
}
System.out.println();
}
// 输出：
// 13 9 5 1
// 14 10 6 2
// 15 11 7 3
// 16 12 8 4
}
}
题解效率也很高。
分析 3
旋转 90 度其实，就相当于先沿着对角线翻转，再沿着中轴线翻转。
也就是说：
①、对角线反转：将矩阵的行和列进行互换。即 matrix[i][j] 变为 matrix[j][i]。
②、中轴线反转：将翻转后的矩阵的每一行进行左右翻转。这样就可以得到旋转 90 度的结果。
textjavascripttypescriptcsshtmlbashjsonmarkdownpythonjavaccpprubygorustphpsqlyaml Copy
class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
// 1. 对角线翻转
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
// 2. 中轴线翻转
for (int i = 0; i < n; i++) {
for (int j = 0; j < n / 2; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[i][n - 1 - j];
matrix[i][n - 1 - j] = temp;
}
}
}
}
来看一下题解效率：
总结
这道题的关键在于找规律：“旋转后的元素和旋转之前的关系”，找不到就记住🤣：
第一种解法中我们用空间换时间，需要借助一个额外的数组；
第二种解法我们把矩阵分成了一层一层，然后逐层旋转；
第三种解法我们先沿着对角线翻转，再沿着中轴线翻转。
其实就在于找到元素下标反转前后的关系。
假设矩阵的大小为 n × n，元素位于原矩阵中的位置为 (i, j)，那么在顺时针旋转 90 度后，元素的新位置应该为 (j, n - 1 - i)。
力扣链接：https://leetcode.cn/problems/rotate-image/
一步一个脚印
不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。
PDF 版本目前只针对二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 加入我们吧。
一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 6200 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！
语雀专栏地址+密码可通过星球置顶帖查看：https://t.zsxq.com/15rEo9Pdu
这道题可以说完全重写了，给出 3 道大家完全都能掌握的题解（ 主要是理解元素反转后下标之间的关系）。
增加代码注释，这样大家更容易看懂并掌握题解；
增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；
增加手绘图，这样大家更容易理解解题思路；
增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；
增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；
图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。
另外，这一版本会作为 PDF 的终稿随后在星球进行发布。