一、题目描述

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 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 == matrix.length == matrix[i].length
• 1 <= n <= 20
• -1000 <= matrix[i][j] <= 1000

二、题目分析

因为题目限制了空间，所以原地翻转的操作，那就是用一个临时变量来存储每次翻转要被覆盖的变量，因为是顺旋转90°，只要四次就会回到原位，所以单个元素的翻转，我们需要统计四个位置上的参数：

• 通过四次交换，将当前层的四个元素旋转到位：
  • matrix[i][j]（左上）与 matrix[n - j - 1][i]（左下）。
  • matrix[n - j - 1][i]（左下）与 matrix[n - i - 1][n - j - 1]（右下）。
  • matrix[n - i - 1][n - j - 1]（右下）与 matrix[j][n - i - 1]（右上）。
  • matrix[j][n - i - 1]（右上）与 temp（保存的左上元素）。

得到思路：

1. 分层旋转：
   • 将矩阵看作由若干层组成的洋葱结构，从外层到内层逐层旋转。
   • 对于每一层，将其分为四个部分：上边、右边、下边和左边。
   • 通过交换这四个部分的元素来实现旋转。
2. 元素交换规则：
   • 对于矩阵中的元素 matrix[i][j]，旋转后的位置为 matrix[j][n-i-1]。
   • 通过四次交换，可以将四个位置的元素旋转到位。
3. 实现步骤：
   • 遍历矩阵的每一层（从外层到内层）。
   • 对于每一层，遍历当前层的元素，按照上述规则进行交换。

对于矩阵的行列的奇偶数还是需要考虑一番，

 当 n 为偶数时

• 枚举位置：需要枚举 �24=(�2)×(�2)4n2​=(2n​)×(2n​) 个位置。
• 划分方式：将矩阵划分为四块，每块的大小为 (�2)×(�2)(2n​)×(2n​)。
• 示例：以 4×44×4 的矩阵为例：
  • 将矩阵分为四个 2×22×2 的块。
  • 通过旋转这四个块，可以保证不重复、不遗漏地完成整个矩阵的旋转。

2. 当 n 为奇数时

• 枚举位置：需要枚举 �2−14=(�−12)×(�+12)4n2−1​=(2n−1​)×(2n+1​) 个位置。
• 划分方式：由于矩阵的中心位置在旋转后保持不变，因此需要采用不同的划分方式。
• 示例：以 5×55×5 的矩阵为例：
  • 中心位置 (2,2)(2,2) 不需要移动。
  • 将矩阵划分为四个部分，每部分的大小为 2×32×3 或 3×23×2（具体取决于划分方式）。
  • 通过旋转这些部分，可以完成整个矩阵的旋转。

具体可以参考这篇题解

作者：力扣官方题解
链接：https://leetcode.cn/problems/rotate-image/solutions/526980/xuan-zhuan-tu-xiang-by-leetcode-solution-vu3m/
来源：力扣（LeetCode）

三、代码实现

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
	        for(int i = 0; i < n/2; i++) {
	        	for(int j = 0; j < (n+1)/2; j++) {
	        		int temp = matrix[i][j];
	        		matrix[i][j] = matrix[n-j-1][i];
	        		matrix[n-j-1][i] = matrix[n-i-1][n-j-1];
	        		matrix[n-i-1][n-j-1] = matrix[j][n-i-1];
	        		matrix[j][n-i-1] = temp;
	        	}
	        }
    }
}

代码解析

1. 外层循环：
   • for (int i = 0; i < n / 2; i++)：遍历矩阵的每一层。n / 2 表示矩阵的层数。
2. 内层循环：
   • for (int j = 0; j < (n + 1) / 2; j++)：遍历当前层的每个元素。(n + 1) / 2 确保奇数层时中间元素被正确处理。
3. 元素交换：
   • 通过四次交换，将当前层的四个元素旋转到位：
     • matrix[i][j]（左上）与 matrix[n - j - 1][i]（左下）。
     • matrix[n - j - 1][i]（左下）与 matrix[n - i - 1][n - j - 1]（右下）。
     • matrix[n - i - 1][n - j - 1]（右下）与 matrix[j][n - i - 1]（右上）。
     • matrix[j][n - i - 1]（右上）与 temp（保存的左上元素）。

提交结果

四、总结

复杂度分析

• 时间复杂度：O(n²)，其中 n 是矩阵的边长。我们需要遍历矩阵的每个元素。
• 空间复杂度：O(1)，只使用了常数级别的额外空间。

1. 核心思想：
   • 将矩阵分层，逐层旋转。
   • 通过四次交换实现 90 度旋转。
2. 关键点：
   • 确定每层的范围（n / 2 和 (n + 1) / 2）。
   • 确保交换的顺序正确，避免覆盖数据。
3. 适用场景：
   • 适用于原地修改矩阵的问题。
   • 可以推广到其他旋转角度（如 180 度、270 度）。