48. 旋转图像

LeetCode 48¹ · 中等 · 矩阵

题

把一个 n × n 矩阵顺时针旋转 90 度，必须原地修改，不能另开一个矩阵。

例：[[1, 2, 3], [4, 5, 6], [7, 8, 9]] → [[7, 4, 1], [8, 5, 2], [9, 6, 3]]。

一句话

先转置（M[i][j] ↔ M[j][i]），再把每一行反转。

关键技巧

看坐标怎么变。 顺时针 90° 把 \((i, j)\) 送到 \((j,\ n-1-i)\)。把这个映射拆成两步：

两步都是「对合」（自己的逆），原地交换就行。 转置是沿对角线的对称，只需交换上三角和下三角（j > i）；行翻转是每行左右对称交换。对称操作两两配对互换，不需要临时缓冲，天然 \(O(1)\) 空间。直接做旋转则是四个元素一轮的环，要一个临时变量、下标更难写。

组合表：

解

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        n = len(matrix)
        for i in range(n):
            for j in range(i + 1, n):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        for row in matrix:
            row.reverse()

时间 \(O(n^2)\)，空间 \(O(1)\)。

延伸

• 四元素轮换法：按层处理，每层对 (i, j) → (j, n-1-i) → (n-1-i, n-1-j) → (n-1-j, i) 四个位置转一圈，每个元素只移动一次，但下标很容易写错。
• 按层处理矩阵的同类：54. 螺旋矩阵。
• 坑：转置时内层循环从 i + 1 开始，写成 range(n) 会把每对交换两次、等于没换。
• Python 里 matrix[:] = [list(r) for r in zip(*matrix[::-1])] 一行也对，但开了新空间，不满足原地要求。

s = Solution()
for mat, want in [
    ([[1, 2, 3], [4, 5, 6], [7, 8, 9]], [[7, 4, 1], [8, 5, 2], [9, 6, 3]]),
    (
        [[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]],
    ),
    ([[1]], [[1]]),
    ([[1, 2], [3, 4]], [[3, 1], [4, 2]]),
]:
    s.rotate(mat)
    assert mat == want