数组与哈希中等2 种解法
#48旋转图像
把 n×n 矩阵顺时针旋转 90 度，推荐原地完成。
#数组#矩阵#原地修改
原题
给定一个 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].length1 <= n <= 20-1000 <= matrix[i][j] <= 1000
解题主线
- 坐标 (row, column) 旋转后变为 (column, n-1-row)。
- 先沿主对角线转置，再逐行反转，等价于顺时针旋转。
解法 1：四点原地轮换
遍历左上区域，每次循环移动同一旋转轨道上的四个元素。
-
时间复杂度： O(n²)
-
空间复杂度： O(1)
final class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
// 该遍历范围让每个四点旋转轨道恰好处理一次。
for (int row = 0; row < n / 2; row++) {
for (int column = 0; column < (n + 1) / 2; column++) {
int temporary = matrix[row][column];
// 按“左下→左上→右上→右下→左下”同步轮换，避免覆盖原值。
matrix[row][column] = matrix[n - 1 - column][row];
matrix[n - 1 - column][row] = matrix[n - 1 - row][n - 1 - column];
matrix[n - 1 - row][n - 1 - column] = matrix[column][n - 1 - row];
matrix[column][n - 1 - row] = temporary;
}
}
}
}解法 2：辅助矩阵坐标映射
把每个原元素写入旋转后的坐标，再整体复制回输入矩阵。
-
时间复杂度： O(n²)
-
空间复杂度： O(n²)
final class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
int[][] rotated = new int[n][n];
// 顺时针旋转的坐标映射为 (row, column) -> (column, n - 1 - row)。
for (int row = 0; row < n; row++) {
for (int column = 0; column < n; column++) {
rotated[column][n - 1 - row] = matrix[row][column];
}
}
// 映射完成后再整体写回，避免读取尚未处理的原矩阵元素时被覆盖。
for (int row = 0; row < n; row++) {
System.arraycopy(rotated[row], 0, matrix[row], 0, n);
}
}
}实现提示
- 保留旧文件中真实不同的辅助空间方案，但面试时优先原地解法。
边界与易错点
- 直接四点轮换时行列下标很容易写反。
- 辅助矩阵方案正确但不是题目要求的严格原地算法。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
medium/Q048_rotate.java