旋转图像

LeetCode 官方题目链接

1. 题目呈现

难度等级：🟡 中等
核心考察点：矩阵、数学、原地算法

给定一个 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]]

---

2. 解题思路拆解

方法：两次翻转

要将一个矩阵顺时针旋转 90 度，可以通过两次简单的数学变换来实现，这样比直接计算旋转后的坐标更容易写代码，也更不容易出错。

旋转 90 度 = 水平翻转 + 对角线翻转 (顺序很重要) 或者 旋转 90 度 = 对角线翻转 + 左右翻转 (这种更常见)

这里我们采用 先水平翻转，再对角线翻转 的策略（或者先上下翻转，再对角线翻转）。

1. 第一步：上下翻转

   • 将矩阵的第 i 行和第 n - 1 - i 行交换。
   • 也就是 matrix[i][j] 和 matrix[n - 1 - i][j] 交换。
   • 变换后，原矩阵的最后一行跑到了第一行，倒数第二行跑到第二行...

2. 第二步：主对角线翻转

   • 沿主对角线（左上到右下）交换元素。
   • 即交换 matrix[i][j] 和 matrix[j][i]。
   • 注意遍历范围是 i 从 0 到 n, j 从 i + 1 到 n（只遍历对角线一侧）。

示例演示： [[1,2,3], [4,5,6], [7,8,9]]

• 上下翻转： [[7,8,9], [4,5,6], [1,2,3]] (1,2,3 到下面去了，7,8,9 到上面来了)
• 对角线翻转： swap(8, 4), swap(9, 1), swap(6, 2)[[7,4,1], [8,5,2], [9,6,3]] 这正是顺时针旋转 90 度的结果！

---

3. 代码实现

/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
var rotate = function(matrix) {
    const n = matrix.length;
    
    // 1. 上下翻转
    for (let i = 0; i < Math.floor(n / 2); i++) {
        for (let j = 0; j < n; j++) {
            const temp = matrix[i][j];
            matrix[i][j] = matrix[n - 1 - i][j];
            matrix[n - 1 - i][j] = temp;
        }
    }
    
    // 2. 主对角线翻转
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) { // 注意 j 从 i + 1 开始
            const temp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = temp;
        }
    }
};

代码执行演示

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

1. 上下翻转：
   • i=0: 交换第 0 行 [1,2,3] 和第 2 行 [7,8,9]。
   • 矩阵变：[[7,8,9], [4,5,6], [1,2,3]]
   • i=1: 1 < 1.5，循环结束。
2. 对角线翻转：
   • i=0:
     • j=1: 交换 (0,1)即8 和 (1,0)即4。矩阵：[[7,4,9], [8,5,6], [1,2,3]]
     • j=2: 交换 (0,2)即9 和 (2,0)即1。矩阵：[[7,4,1], [8,5,6], [9,2,3]]
   • i=1:
     • j=2: 交换 (1,2)即6 和 (2,1)即2。矩阵：[[7,4,1], [8,5,2], [9,6,3]]
   • i=2:
     • j=3: 循环不执行。

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

---

4. 复杂度分析

维度	描述
时间复杂度	$O(n^2)$。我们需要遍历矩阵两次，元素总数为 $n^2$。
空间复杂度	$O(1)$。原地旋转，只需要常数级别的额外空间用于交换。