BM99　顺时针旋转矩阵¶

中等通过率 53.34%python3核心代码模式样例通过牛客 AC数组基础数学

讲解章节：模拟

一句话

先沿主对角线转置，再左右翻转每一行，原地完成。

解题思路¶

这题考什么¶

把一个整体的下标映射拆成两个各自平凡的对合操作。顺时针转 90 度的映射是 new[i][j] = old[n-1-j][i]；照这个式子往新矩阵里填是 O(n^2) 时间、O(n^2) 空间，一行推导式就能写完。但题面的进阶要求空间 O(1)，就得原地做，于是拆成两步：

1) 转置（沿主对角线翻）：mat[i][j] 与 mat[j][i] 互换
2) 每一行左右翻转

验证等价性：转置后位置 (i, j) 放的是 old[j][i]；再把第 i 行左右翻转，(i, j) 处换成转置矩阵的 (i, n-1-j)，即 old[n-1-j][i]，与目标映射完全一致。

3x3 走一遍：

1 2 3      转置      1 4 7     每行翻转     7 4 1
4 5 6      ---->     2 5 8     ------->     8 5 2
7 8 9                3 6 9                  9 6 3

逆时针 90 度只需把第二步换成「上下翻转行的顺序」（转置 + 翻行）。

数据规模与复杂度¶

0 < n < 300，元素 0 <= val <= 1000，时限「其他语言 2 秒」。转置扫上三角约 n^2 / 2 次交换，翻行再动 n^2 / 2 次，时间 O(n^2)（n = 299 时不到 9 万次操作），空间 O(1)——全是原地交换。按映射新建矩阵的写法是 O(n^2) 空间，能过但拿不到进阶分。

坑在哪¶

转置只能扫上三角，内层从 j = i + 1 起。写成 j 从 0 到 n-1，每一对元素会被交换两次，等于没换，矩阵原样不动—— 这是本题最隐蔽的错误，因为对称矩阵的样例照样能过。
内层起点 i + 1 而不是 i：对角线上的元素 mat[i][i] 与自己交换是空操作，跳过它只是省一次无用的赋值，写成 i 也不影响正确性，但把 i + 1 误写成 i - 1 就会重新扫进下三角。
两步的先后不能换。先翻行再转置得到的是逆时针 90 度，正好差了个方向。
行内翻转用列表自身的 reverse，它是原地的；写成 row = row[::-1] 只会让循环变量指向一个新列表，矩阵里那一行纹丝不动。
签名要求返回 integer[][]，原地改完把 mat 返回即可。 n <= 0 或空矩阵时两层循环都不进入，直接把原矩阵交回去。

参考实现¶

solutions/nowcoder/BM99/sol.py
from typing import List, Optional


class Solution:
    def rotateMatrix(self, mat: List[List[int]], n: int) -> List[List[int]]:
        # 1) 沿主对角线转置：内层从 j = i + 1 起，只扫上三角。
        #    若 j 从 0 起，每一对元素会被交换两次，等于白换
        for i in range(n):
            for j in range(i + 1, n):
                mat[i][j], mat[j][i] = mat[j][i], mat[i][j]
        # 2) 每行左右翻转，与转置合起来正好是顺时针 90 度；
        #    用列表自带的 reverse 就地改写，切片反转只会换掉循环变量的指向
        for row in mat:
            row.reverse()
        return mat                # 签名要求返回矩阵，原地改完把入参交回去

BM99 顺时针旋转矩阵¶