LeetCode 面试题 01.07. 旋转矩阵

2024-10-06 HGNULB 约 4 分钟

文章信息 11 个分类 3 个标签

分类

LeetCode CodeTop 中等未解决 10-20 字节跳动快手腾讯百度拼多多程序员面试金典（第 6 版）

题目描述

✅ 面试题 01.07. 旋转矩阵

题意分析

给定一个 $N \times N$ 的方阵，把它整体顺时针转 90 度，并且要求「原地」完成。

约束里有两个关键信号。第一，矩阵是正方形，行数等于列数，旋转后形状不变，所以才可能在同一块内存上改；如果是 $M \times N$ 的长方形，行列数会互换，原地就无从谈起。第二，题目明确说不能占用额外的矩阵空间，这排除了「新开一个数组按公式抄过去」这种一行就能想到的写法，逼你在原数组上做交换。

先把「顺时针 90 度」写成坐标映射，后面所有推导都以它为准：原来位于第 row 行第 col 列的元素，转完之后位于第 col 行第 n - 1 - row 列。可以用第一行验证直觉——原来的第一行会竖着贴到最右边一列，原来的第一列会横着躺到最上面一行。

边界有三处：n = 1 时不需要做任何事；n 为偶数时元素两两对称，没有落单的；n 为奇数时主对角线上的元素旋转前后仍在自己该在的相对位置上，不需要与谁交换。

解法：先转置再反转每一行

核心思路

顺时针旋转 90 度的坐标映射是：原位置 (row, col) 移到 (col, n - 1 - row)。直接按这个公式写入新矩阵很容易，但需要 $O(n^2)$ 额外空间，不符合原地要求。

也可以每次让四个对称位置循环交换，但需要同时写对四组下标和遍历边界。把旋转拆成两个熟悉的原地操作，代码更短，也更容易用坐标映射验证方向。

可以把映射拆成两次原地变换：

沿主对角线转置：(row, col) -> (col, row)；

反转每一行：(col, row) -> (col, n - 1 - row)。

两步复合正好得到目标映射。转置时只交换主对角线一侧的元素，否则同一对位置交换两次会回到原状。

两个阶段各有清晰不变量：转置完成后，新位置 (row, col) 保存原位置 (col, row) 的值；行反转完成后，它进一步来自原位置 (n - 1 - col, row)，这正是顺时针旋转后的逆向坐标关系。

解题步骤

遍历严格上三角区域，即 col > row，交换 matrix[row][col] 与 matrix[col][row]。

对每一行使用左右双指针，原地反转该行。

两个阶段结束后矩阵即为顺时针旋转结果，无需返回新矩阵。

例如 [[1,2,3],[4,5,6],[7,8,9]] 转置后是 [[1,4,7],[2,5,8],[3,6,9]]，逐行反转后得到 [[7,4,1],[8,5,2],[9,6,3]]。

代码实现

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;

        for (int row = 0; row < n; row++) {
            for (int col = row + 1; col < n; col++) {
                int value = matrix[row][col];
                matrix[row][col] = matrix[col][row];
                matrix[col][row] = value;
            }
        }

        for (int[] row : matrix) {
            for (int left = 0, right = n - 1; left < right; left++, right--) {
                int value = row[left];
                row[left] = row[right];
                row[right] = value;
            }
        }
    }
}

func rotate(matrix [][]int) {
    n := len(matrix)

    for row := 0; row < n; row++ {
        for col := row + 1; col < n; col++ {
            matrix[row][col], matrix[col][row] = matrix[col][row], matrix[row][col]
        }
    }

    for row := 0; row < n; row++ {
        for left, right := 0, n-1; left < right; left, right = left+1, right-1 {
            matrix[row][left], matrix[row][right] = matrix[row][right], matrix[row][left]
        }
    }
}

复杂度分析

时间复杂度：$O(n^2)$。转置与逐行反转都只遍历矩阵常数次。

空间复杂度：$O(1)$。所有交换都在原矩阵内完成。

关键点总结

先写出坐标映射，再将复杂变换拆成“转置 + 行反转”。

转置只遍历主对角线的一侧，避免重复交换。

转置后反转每一行得到顺时针旋转；方向改变时，反转的维度也会改变。

方阵旋转后行列尺寸不变，才适合这种原地做法。

易错点总结

转置时遍历整个矩阵，会把每对元素交换两次，等于没有转置。

只转置不反转，得到的是关于主对角线的镜像，不是旋转。

转置后反转每一列会得到逆时针旋转。

直接按目标坐标原地覆盖，会在原值被读取前将其破坏。

行反转的右指针应从 n - 1 开始，不能写成 n。

相似题目

题目	难度	考察点
48. 旋转图像	中等	同题不同编号的原地旋转
867. 转置矩阵	简单	单独考察转置与非方阵
73. 矩阵置零	中等	借首行首列做原地标记
面试题 01.08. 零矩阵	中等	置零问题的金典版本
54. 螺旋矩阵	中等	四边界收缩的顺时针遍历
59. 螺旋矩阵 II	中等	按螺旋顺序填充数字
289. 生命游戏	中等	原地状态压缩与同步更新