旋转图像 - Stellar Observer Protocol

516 字

3 分钟

旋转图像

2025-08-28

Algorithms

矩阵

/

数学

/

数组

题目描述#

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

解题思路#

分层旋转：
- 将矩阵视为同心方框，从外层向内层旋转
元素分组交换：
- 每层分为4个元素一组（四个角）
- 每组元素顺时针轮换位置
索引映射：
- 计算旋转后坐标关系：(i,j) → (j,n-1-i)
临时变量辅助：
- 使用单个临时变量完成4个元素的交换
范围控制：
- 外层循环处理 n//2 层
- 内层循环处理 n-2*i-1 个元素

关键洞察#

旋转等价性：
- 顺时针90° = 转置 + 水平翻转
- 逆时针90° = 转置 + 垂直翻转
位置映射规律：
- matrix[i][j] → matrix[j][n-1-i]
分层优化：
- 避免整体转置的内存开销
原地操作：
- 仅需常数额外空间
对称性利用：
- 每组4个元素构成闭环交换

复杂度分析#

指标	说明
时间复杂度	O(n²)：每个元素访问一次
空间复杂度	O(1)：仅需常数临时空间
最优情况	O(1)：1x1矩阵
最坏情况	O(n²)：大尺寸矩阵

代码实现#

1
/**
2
 * @param {number[][]} matrix
3
 * @return {void} Do not return anything, modify matrix in-place instead.
4
 */
5
var rotate = function (matrix) {
6
    const n = matrix.length;
7
    for (let i = 0; i < Math.floor(n / 2); i++) {
8
        for (let j = 0; j < Math.floor((n + 1) / 2); j++) {
9
            const temp = matrix[i][j];
10
            matrix[i][j] = matrix[n - j - 1][i];
11
            matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
12
            matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
13
            matrix[j][n - i - 1] = temp;
14
        }
15
    }
16
};