旋转图像

---

题目描述

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

原地算法：在计算机科学中，一个原地算法（in-place algorithm）是一种使用小的，固定数量的额外之空间来转换资料的算法。当算法执行时，输入的资料通常会被要输出的部分覆盖掉。不是原地算法有时候称为非原地（not-in-place）或不得其所（out-of-place）。

示例 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, ], [12, 6, 8, 9], [16, 7, 10, 11]]

提示:

• n == matrix.length == matrix[i].length
• 1 <= n <= 20
• -1000 <= matrix[i][j] <= 1000

原地旋转法

核心思路

通过一次旋转四个元素实现原地旋转。对于每个位置 (i, j)，我们找到旋转后对应的三个位置，使用临时变量完成四个元素的交换。旋转过程如下：

1. 左上角元素 → 右上角
2. 右上角元素 → 右下角
3. 右下角元素 → 左下角
4. 左下角元素 → 左上角

旋转公式推导

设矩阵大小为 n，对于位置 (i, j)：

1. 左上角：(i, j)
2. 右上角：(j, n-1-i)
3. 右下角：(n-1-i, n-1-j)
4. 左下角：(n-1-j, i)

temp = matrix[i][j]
matrix[i][j] = matrix[n-1-j][i]         // 左下 → 左上
matrix[n-1-j][i] = matrix[n-1-i][n-1-j] // 右下 → 左下
matrix[n-1-i][n-1-j] = matrix[j][n-1-i] // 右上 → 右下
matrix[j][n-1-i] = temp                 // 左上 → 右上

遍历范围优化

• 当 n 为偶数时：遍历左上角 1/4 区域
• 当 n 为奇数时：遍历左上角 1/4 + 中心轴 区域

图形化示例

初始矩阵：
[1, 2, 3]
[4, 5, 6]
[7, 8, 9]

步骤1：旋转(0,0)元素
  1 → 3的位置，3 → 9的位置，9 → 7的位置，7 → 1的位置
得到：
[7, 2, 1]
[4, 5, 6]
[9, 8, 3]

步骤2：旋转(0,1)元素
  2 → 6的位置，6 → 8的位置，8 → 4的位置，4 → 2的位置
得到：
[7, 4, 1]
[8, 5, 2]
[9, 6, 3]

最终结果：
[7, 4, 1]
[8, 5, 2]
[9, 6, 3]

代码实现

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;
        }
    }
}

复杂度分析

• 时间复杂度：O(n²)，其中 n 是 matrix 的边长。
• 空间复杂度：O(1)，为原地旋转。

翻转组合法

核心思路

通过两次翻转操作实现旋转：

1. 水平翻转（上下翻转）：matrix[i][j] ↔ matrix[n-1-i][j]
   • 以水平中线为轴交换元素
   • 行索引变换：i → n-1-i
   • 列索引不变
2. 主对角线翻转（转置）：matrix[i][j] ↔ matrix[j][i]
   • 沿主对角线（左上到右下）交换元素
   • 行列索引互换：(i, j) → (j, i)
   • 只需遍历对角线一侧避免重复

推导步骤

1. 水平翻转后：(i, j) → (n-1-i, j)
2. 主对角线翻转后：(n-1-i, j) → (j, n-1-i)
3. 与顺时针旋转 90° 的坐标变换一致：(i, j) → (j, n-1-i)

图形化示例

初始矩阵：
[1, 2, 3]
[4, 5, 6]
[7, 8, 9]

步骤1：水平翻转
  交换行：第0行 ↔ 第2行
得到：
[7, 8, 9]
[4, 5, 6]
[1, 2, 3]

步骤2：主对角线翻转
  交换(1,0)和(0,1)：8 ↔ 4
  交换(2,0)和(0,2)：9 ↔ 1 → 但实际顺序：先1和9交换，再2和6交换
  详细过程：
    [7, 8, 9]    [7, 4, 9]    [7, 4, 1]    [7, 4, 1]
    [4, 5, 6] → [8, 5, 6] → [8, 5, 6] → [8, 5, 2]
    [1, 2, 3]    [1, 2, 3]    [9, 2, 3]    [9, 6, 3]

最终结果：
[7, 4, 1]
[8, 5, 2]
[9, 6, 3]

代码实现

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;
        }
    }
}

复杂度分析

• 时间复杂度：O(n²)，其中 n 是 matrix 的边长。
• 空间复杂度：O(1)，为原地旋转。

总结

解法	时间复杂度	空间复杂度	优势
原地旋转法	O(n²)	O(1)	通过数学推导直接定位旋转位置，单次循环完成操作
翻转组合法	O(n²)	O(1)	利用基础操作组合实现旋转，逻辑清晰易理解

两种方法都满足原地旋转的要求，在实际应用中可根据具体场景选择。翻转组合法更易于理解和扩展（如逆时针旋转只需调整翻转顺序），而原地旋转法在理论上减少了一半的交换操作。

来源

48. 旋转图像 | 力扣（LeetCode）

---