LC48　旋转图像¶

中等通过率 79.5%python3核心代码模式矩阵样例通过牛客 AC数组数学矩阵

一句话

先沿主对角线转置，再把每一行左右翻转，两步原地完成顺时针 90 度。

解题思路¶

这题考什么¶

先把「顺时针转 90 度」写成下标映射。原来在第 i 行第 j 列的元素，转完之后落在第 j 行第 n-1-i 列：

new[j][n - 1 - i] = old[i][j]

验证一下 n = 3 的左上角 old[0][0]：它应当跑到右上角 new[0][2]，代入得 new[0][2]，对上了；old[0][2]（右上角）跑到 new[2][2]（右下角），也对。所以映射没写反。

直接照映射把元素搬到新矩阵是 O(n^2) 额外空间，题目明确禁止再开一个矩阵。 把这个映射拆成两个更简单的映射之积就能原地做：

转置（沿主对角线镜像）      t[j][i] = old[i][j]
每行左右翻转                r[j][n - 1 - i] = t[j][i] = old[i][j]

右边正好就是要的 new。两步各自都是成对交换，天然原地。

为什么拆成这两步而不是别的：转置只交换 (i, j) 与 (j, i)，行翻转只交换同一行内的两列，两者都不需要临时矩阵，也不需要考虑「搬走的元素往哪放」。这类原地重排手法见序列与数组。

另一条路是四点轮转：把矩阵划成若干同心方环，每次取环上互成 90 度的四个位置 (i, j) -> (j, n-1-i) -> (n-1-i, n-1-j) -> (n-1-j, i) -> (i, j)，存一个临时变量，四个值沿环挪一格。它只写一遍元素、常数更小，但两处极易写错，见「坑在哪」第 2、3 条。转置加翻转写两遍元素， n <= 20 时这点差别可以忽略，换来的是几乎不可能写错的代码。

数据规模与复杂度¶

n == matrix.length == matrix[i].length，1 <= n <= 20， -1000 <= matrix[i][j] <= 1000。矩阵一定是方阵，这是原地旋转成立的前提—— 非方阵旋转后形状都变了，装不回原来的容器。时间 O(n^2)：转置扫上三角约 n^2 / 2 次交换，行翻转再约 n^2 / 2 次。空间 O(1)。n 最大 20，总共 400 个格子，效率不是这题的考点。

坑在哪¶

转置只能遍历上三角，内层从 j = i + 1 起。写成 for j in range(n) 会把每一对 (i, j) 与 (j, i) 交换两次，第二次原样换回去，结果等于什么都没做，矩阵纹丝不动。起点写 j = i 也行（对角线元素与自己交换，无害但白做一次），写 j = 0 就是错的。
四点轮转的赋值方向必须是「倒着拉」而不是「顺着推」。先把 (i, j) 存进临时变量后，接下来要写的是 matrix[i][j] = matrix[n-1-j][i]—— 从逆时针方向的源头拉数据过来；一路拉到最后再把临时变量放回去。若顺着旋转方向写成 matrix[j][n-1-i] = matrix[i][j] 开头，目标位置的原值还没救出来就被覆盖，那一整环会被同一个值刷满。
四点轮转的遍历范围是 for i in range(n // 2) 配 for j in range(i, n - 1 - i)，内层是半开区间、右端不含 n-1-i。范围取大了（比如内层写 range(i, n - i)）会把每个环的四个角各多转一次，实测 n = 3 的样例得到 [[9,4,7],[8,5,2],[3,6,1]] 而非正确的 [[7,4,1],[8,5,2],[9,6,3]]——角落被转成了 180 度；范围取小了则漏掉每条边的最后一格。这两个边界正是四点轮转难写对的地方，也是本题解选转置加翻转的理由。
行翻转是把每行整行首尾对调，不是只翻某一段。翻转用相向双指针 while lo < hi，用 <= 会让 n 为奇数时中间那一格与自己交换（无害但多此一举），而真正的错误是把区间写窄，比如只翻到 n // 2 - 1。
切片赋值 matrix[i] = matrix[i][::-1] 在力扣判题下能过（判的是最外层 list 的内容），但它给外层 list 挂上了一个新的行对象，原来那些行并没有被改动。调用方若持有原行的引用就会读到旧数据，这已经不算「直接修改输入的二维矩阵」。本题解用双指针在原行对象上交换，语义上才是真正的原地。
两步的顺序不能颠倒。先翻转每行再转置得到的是逆时针 90 度： [[1,2,3],[4,5,6],[7,8,9]] 先翻行得 [[3,2,1],[6,5,4],[9,8,7]]，再转置得 [[3,6,9],[2,5,8],[1,4,7]]，而顺时针的答案是 [[7,4,1],[8,5,2],[9,6,3]]。
返回值是 None，答案留在入参 matrix 里。签名的返回类型是 void，判题机调用完之后回头读第 0 个参数。任何形如 matrix = ... 的重新绑定都不会被判题机看见，必须原地写。
严格比对：旋转结果唯一，没有多解。

样例复核¶

matrix = [[1,2,3],[4,5,6],[7,8,9]]，期望 [[7,4,1],[8,5,2],[9,6,3]]。

转置（沿主对角线镜像，交换 (0,1)(0,2)(1,2) 三对）
    1 2 3        1 4 7
    4 5 6   ->   2 5 8
    7 8 9        3 6 9
每行左右翻转
    1 4 7        7 4 1
    2 5 8   ->   8 5 2
    3 6 9        9 6 3

与样例一致。用下标映射再核一次：old[0][0] = 1 应落到 new[0][2]，终态第 0 行第 2 列确实是 1。

参考实现¶

solutions/leetcode/LC48/sol.py
from typing import List, Optional


class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        n = len(matrix)
        # 第一步：沿主对角线转置，把 (i, j) 与 (j, i) 对调
        for i in range(n):
            # 内层从 i + 1 起，只扫上三角。写成 range(n) 会把每一对交换两次，
            # 第二次原样换回去，矩阵等于没动
            for j in range(i + 1, n):
                # 两个下标都是普通变量、互不依赖，元组交换在这里是安全的
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        # 第二步：每一行左右翻转。转置后的 t[j][i] 再做列的镜像，
        # 得到 t[j][n - 1 - i]，正是顺时针 90 度要求的 new[j][n - 1 - i] = old[i][j]。
        # 两步顺序不能反：先翻行再转置得到的是逆时针 90 度
        for row in matrix:
            # 相向双指针在**原行对象**上交换，而不是 row[::-1] 换一个新 list，
            # 这样才真正满足「直接修改输入的二维矩阵」
            lo = 0
            hi = n - 1
            while lo < hi:
                row[lo], row[hi] = row[hi], row[lo]
                lo += 1
                hi -= 1
        # 不返回任何东西：答案留在入参 matrix 里，判题机调用完之后回头读它

LC48 旋转图像¶