【忍者算法】从照片旋转到矩阵变换：探索图像旋转问题｜LeetCode 48 旋转图像

从照片旋转到矩阵变换：探索图像旋转问题

生活中的旋转

在这个自拍时代，我们经常需要调整照片的方向。有时拍出来的照片歪了，需要旋转90度；有时想要换个角度看看效果，来回旋转照片。这种旋转操作不仅存在于我们的日常生活中，在计算机图形学、图像处理等领域也是一个基础且重要的操作。
问题描述

LeetCode第48题"旋转图像"要求我们：给定一个 n × n 的二维矩阵 matrix 表示一个图像，将图像顺时针旋转 90 度。要求必须在原地旋转图像，也就是说，你需要直接修改输入的二维矩阵。
例如：

1. 输入：matrix = [[1,2,3],
2.                 [4,5,6],
3.                 [7,8,9]]
4. 输出：[[7,4,1],
5.        [8,5,2],
6.        [9,6,3]]

复制代码

就像我们在手机相册里旋转照片一样，每个像素点都要移动到新的位置，但我们需要保证不使用额外的存储空间！
最直观的解法：辅助数组

最简单的想法就像我们复印一张照片，在新的纸上重新排列像素。虽然这种方法使用了额外空间，不符合题目要求，但它帮助我们理解旋转的本质。
辅助数组的实现

1. public void rotate(int[][] matrix) {
2.     int n = matrix.length;
3.     // 创建一个新的n×n数组
4.     int[][] temp = new int[n][n];
5.    
6.     // 将原矩阵旋转90度后的结果存入临时数组
7.     for (int i = 0; i < n; i++) {
8.         for (int j = 0; j < n; j++) {
9.             // 关键转换：第i行第j列的元素，旋转后变成第j行第(n-1-i)列
10.             temp[j][n-1-i] = matrix[i][j];
11.         }
12.     }
13.    
14.     // 将结果复制回原矩阵
15.     for (int i = 0; i < n; i++) {
16.         for (int j = 0; j < n; j++) {
17.             matrix[i][j] = temp[i][j];
18.         }
19.     }
20. }

复制代码

优化解法：原地旋转

仔细观察，我们发现90度旋转可以通过两步简单的操作完成：先沿对角线翻转，再沿竖直中线翻转。就像折纸一样，通过两次折叠就能达到旋转的效果！
原地旋转的原理

想象你在玩魔方：

• 第一步：沿主对角线翻转（左上到右下的对角线）
  
  
  
  • [i,j] 变成 [j,i]
    
  
  
• 第二步：沿竖直中线翻转
  
  
  
  • [i,j] 变成 [i,n-1-j]
    
  
  

示例运行

用3×3矩阵来说明：

1. 原始矩阵：    对角线翻转：    竖直中线翻转：
2. 1 2 3         1 4 7          7 4 1
3. 4 5 6   →     2 5 8    →     8 5 2
4. 7 8 9         3 6 9          9 6 3
6. 第一步：对角线翻转
7. - (1,2)和(2,1)交换
8. - (1,3)和(3,1)交换
9. - (2,3)和(3,2)交换
11. 第二步：竖直中线翻转
12. - 第1列和第3列交换
13. - 第2列保持不变

复制代码

Java代码实现

1. public void rotate(int[][] matrix) {
2.     int n = matrix.length;
3.    
4.     // 步骤1：沿主对角线翻转
5.     for (int i = 0; i < n; i++) {
6.         for (int j = i; j < n; j++) {
7.             // 交换matrix[i][j]和matrix[j][i]
8.             int temp = matrix[i][j];
9.             matrix[i][j] = matrix[j][i];
10.             matrix[j][i] = temp;
11.         }
12.     }
13.    
14.     // 步骤2：沿竖直中线翻转
15.     for (int i = 0; i < n; i++) {
16.         for (int j = 0; j < n/2; j++) {
17.             // 交换matrix[i][j]和matrix[i][n-1-j]
18.             int temp = matrix[i][j];
19.             matrix[i][j] = matrix[i][n-1-j];
20.             matrix[i][n-1-j] = temp;
21.         }
22.     }
23. }

复制代码

解法比较

让我们比较这两种方法：
辅助数组法：

• 时间复杂度：O(n²)
  
• 空间复杂度：O(n²)
  
• 优点：直观易懂，容易实现
  
• 缺点：需要额外空间，不满足原地旋转的要求
  

原地旋转法：

• 时间复杂度：O(n²)
  
• 空间复杂度：O(1)
  
• 优点：不需要额外空间，完美满足题目要求
  
• 缺点：需要理解矩阵变换的数学原理
  

实用技巧总结

解决矩阵旋转问题的关键点：

• 观察旋转前后元素位置的对应关系
  
• 寻找可以分解的子操作（如翻转）
  
• 正确处理边界情况
  
• 小心不要重复交换元素
  

相关的矩阵变换问题：

• 矩阵转置
  
• 矩阵对称变换
  
• 顺时针/逆时针旋转任意角度
  

小结

通过旋转图像这道题，我们学会了如何通过巧妙的数学变换来完成矩阵旋转。这种思维方式不仅能解决算法题，在图像处理、计算机图形学等领域都有广泛应用。记住，当遇到需要变换矩阵的问题时，可以考虑将复杂的变换分解为简单的操作组合，这样往往能得到更优雅的解决方案！
作者：忍者算法
公众号：忍者算法
我准备了一份刷题清单，以及这些题目的详细题解，覆盖了绝大部分常见面试题。我可以很负责任地说，只要你把这些题真正掌握了，80%的算法面试都能遇到相似题目。公众号回复【刷题清单】获取～

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！