48. 旋转图像（中等）

Blind 75 › 48. 旋转图像（中等） （第 1 章）
文章工具

题目

给定一个 n × n 的方阵 matrix，把它当作一张图片。你要把整张图片顺时针旋转 90°。

额外限制：必须原地完成——直接修改输入的 matrix，不能用另一个矩阵暂存结果。

自造示例：[[1,2],[3,4]] → [[3,1],[4,2]]；[[10,20,30],[40,50,60],[70,80,90]] → [[70,40,10],[80,50,20],[90,60,30]]。

约束：输入是 n × n 方阵，1 ≤ n ≤ 20；元素范围为 -1000 ≤ matrix[i][j] ≤ 1000。

思路

一句话：把 90° 旋转拆成两个已经会做的原地操作——先沿主对角线转置，再对每一行做左右反转。

先想最直白的做法：另开一个 n × n 的新矩阵，按位置映射 new[r][c] = old[n-1-c][r] 把每个元素搬到新家。这样做每个元素只处理一次，时间 O(n2)，但要额外占用 O(n2) 空间。题目明确禁止另开矩阵，所以不行。

要省掉这个新矩阵，先看旋转的对称性：方阵转 90° 之后仍然是同尺寸的方阵，而且每一个格子都有唯一的新位置，谁也不会被谁覆盖。换句话说，旋转只是把 n2 个元素做了一次“置换”，原地完成时只需要一个临时变量来打破搬运链。

关键观察是，这个置换还能进一步拆成两个更简单的置换：

  • 先沿主对角线转置：把 matrix[i][j] 与 matrix[j][i] 互换。
  • 再对每一行做左右反转：让第 i 行整体倒序。

验证角标：位置 (i,j) 转置后到 (j,i)，再反转这一行后到 (j, n-1-i)；而顺时针 90° 的映射正是 new[r][c] = old[n-1-c][r]。代入 r=j, c=n-1-i 得 old[n-1-(n-1-i)][j] = old[i][j]，完全一致。

另一条等价路线是“一圈一圈四角轮换”：左上 → 右上 → 右下 → 左下 → 左上，每次用临时变量咬住一个值。两条路线复杂度相同，本文选更好记、更不容易写错的“转置 + 行反转”。

解法

遍历步骤如下：

  1. 转置：只交换主对角线右上方的部分，避免同一对元素换两次又换回去。
  2. 行反转：逐行调用 reverse(matrix[i]

    🔒

    本篇为付费内容

    您已阅读试读部分，购买后即可解锁全文。

    ⚠️ 本站内容已做唯一性标记并受版权保护，未经授权禁止转载，侵权必究。