vvrf / DSA.log

问题拆解

把 n x n 矩阵原地顺时针旋转 90°，不许开新矩阵。直接想“原地旋转”会很别扭：一个元素要挪到新位置，新位置上的元素又得先挪走，四个位置连成一个环，写四元轮换的下标极容易出错。

换个思路：旋转是一种刚体变换，而刚体变换可以拆成镜像的组合。先看坐标——顺时针转 90° 后，(i, j) 落到 (j, n-1-i)。把这一步拆开：转置把 (i, j) 送到 (j, i)，行内左右反转再把 (j, i) 送到 (j, n-1-i)。两步复合，恰好就是目标位置。

复杂的位置变换拆成两次简单的镜像：转置（沿主对角线翻）+ 每行反转（沿竖直中轴翻），每一步都只是简单的交换。

转置加行反转

转置时内层循环从 i+1 开始，只扫上三角——如果扫整个矩阵，每对元素会被交换两次，等于没换。

public void rotate(int[][] matrix) {
    int n = matrix.length;
    // 沿主对角线转置，只扫上三角
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int t = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = t;
        }
    }
    // 每行左右反转
    for (int[] row : matrix) {
        for (int l = 0, r = n - 1; l < r; l++, r--) {
            int t = row[l];
            row[l] = row[r];
            row[r] = t;
        }
    }
}

def rotate(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()

func rotate(matrix [][]int) {
    n := len(matrix)
    // 沿主对角线转置，只扫上三角
    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        }
    }
    // 每行左右反转
    for _, row := range matrix {
        slices.Reverse(row)
    }
}

pub fn rotate(matrix: &mut Vec<Vec<i32>>) {
    let n = matrix.len();
    // 沿主对角线转置，只扫上三角
    for i in 0..n {
        for j in i + 1..n {
            let t = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = t;
        }
    }
    // 每行左右反转
    for row in matrix.iter_mut() {
        row.reverse();
    }
}

两步的顺序不能换：先反转再转置得到的是逆时针 90°。可以拿左上角验证一下——第一行经过转置变成第一列，再经行反转，第一列跑到了最后一列，正是顺时针旋转后第一行该去的地方。如果面试里被追问“逆时针怎么办”，答案对称：转置后改成每列上下反转，或者先反转每行再转置。

复杂度

指标	复杂度	原因
时间	`O(n^2)`	转置和反转各扫一遍矩阵
空间	`O(1)`	全部是原地交换

可以迁移的模式

旋转 = 两次镜像的复合，90°、180°、逆时针都能用“转置 + 某方向反转”拼出来；
原地交换类操作要想清楚扫描范围（上三角、半行），避免交换两次抵消；
先用坐标公式 (i, j) -> (j, n-1-i) 验证变换正确，再动手写代码。

与其背四元轮换的下标，不如记住“旋转可拆成镜像”这一条，现场就能推出来。