旋转图像 | 秋招知识库

题目链接 · 灵神原题解（署名来源）

题意

把一个方阵（ $n \times n$ 的矩阵）顺时针旋转 $90^{\circ}$ 。

要求：不能创建另一个矩阵，空间复杂度必须是 $O (1)$ 。

分析

顺时针旋转 $90^{\circ}$ 后，位于 $(i, j)$ 的元素去哪了？

竖着看：

第一列的元素去到第一行。
第二列的元素去到第二行。
……
第 $j$ 列的元素去到第 $j$ 行。

横着看：

第一行的元素去到最后一列。
第二行的元素去到倒数第二列。
……
第 $i$ 行的元素去到第 $n - 1 - i$ 列。（ $i$ 从 $0$ 开始）

所以位于 $i$ 行 $j$ 列的元素，去到 $j$ 行 $n - 1 - i$ 列，即 $(i, j) \to (j, n - 1 - i)$ 。

两次翻转等于一次旋转

$(i, j) \to (j, n - 1 - i)$ 可以通过两次翻转操作得到：

(i, j) \overset{转 置}{\to} (j, i) \overset{行 翻 转}{\to} (j, n - 1 - i)

转置：把矩阵按照主对角线翻转，位于 $(i, j)$ 的元素去到 $(j, i)$ 。
行翻转：把每一行翻转，位于 $(j, i)$ 的元素去到 $(j, n - 1 - i)$ 。

示例 1 的操作过程如下：

[\begin{matrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{matrix}] \overset{转 置}{\to} [\begin{matrix} 1 & 4 & 7 \\ 2 & 5 & 8 \\ 3 & 6 & 9 \end{matrix}] \overset{行 翻 转}{\to} [\begin{matrix} 7 & 4 & 1 \\ 8 & 5 & 2 \\ 9 & 6 & 3 \end{matrix}]

注：一般地，把一个点绕 $O$ 旋转任意 $θ$ 角度，可以通过两个翻转操作实现。要求这两条翻转的对称轴，交点为 $O$ 且夹角为 $\frac{θ}{2}$ 。对于本题，每个元素需要绕矩阵中心顺时针旋转 $90^{\circ}$ ，这可以通过关于主对角线翻转，关于垂直中轴翻转实现。这两条对称轴的交点为矩阵中心，且夹角为 $45^{\circ}$ 。

实现

转置：把主对角线下面的元素 $matrix [i] [j]$ 和（关于主对角线）对称位置的元素 $matrix [j] [i]$ 交换。
行翻转：遍历每一行 $row = matrix [i]$ ，把左半边的元素 $row [j]$ 和（关于垂直中轴）对称位置的元素 $row [n - 1 - j]$ 交换。或者，使用库函数翻转 $row$ 。

这两步操作都可以原地实现。

写法一

Python 解法1C++ 解法1

python

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        n = len(matrix)
        # 第一步：转置
        for i in range(n):
            for j in range(i):  # 遍历对角线下方元素
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

        # 第二步：行翻转
        for row in matrix:
            row.reverse()

cpp

// C++ 版待补充

C++ 解法2

cpp

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        // 第一步：转置
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) { // 遍历对角线下方元素
                swap(matrix[i][j], matrix[j][i]);
            }
        }

        // 第二步：行翻转
        for (auto& row : matrix) {
            ranges::reverse(row);
        }
    }
};

写法二

把两个循环合并成一个循环。

需要把遍历顺序调整为遍历对角线上方元素，这样每行遍历完后，这一行的元素后面不会再访问到，可以直接做行翻转。

Python 解法3C++ 解法3

python

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        n = len(matrix)
        for i, row in enumerate(matrix):
            for j in range(i + 1, n):  # 遍历对角线上方元素，做转置
                row[j], matrix[j][i] = matrix[j][i], row[j]
            row.reverse()  # 行翻转

cpp

// C++ 版待补充

C++ 解法4

cpp

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) { // 遍历对角线上方元素，做转置
                swap(matrix[i][j], matrix[j][i]);
            }
            ranges::reverse(matrix[i]); // 行翻转
        }
    }
};

复杂度分析

时间复杂度： $O (n^{2})$ ，其中 $n$ 是 $matrix$ 的行数和列数。
空间复杂度： $O (1)$ 。

思考题

改成顺时针旋转 $180^{\circ}$ ，要怎么做？
改成顺时针旋转 $270^{\circ}$ （逆时针旋转 $90^{\circ}$ ），要怎么做？

欢迎在评论区分享你的思路/代码。

相似题目

189. 轮转数组

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

题意 ​

分析 ​

两次翻转等于一次旋转 ​

实现 ​

写法一 ​

写法二 ​

复杂度分析 ​

思考题 ​

相似题目 ​

分类题单 ​

题意

分析

两次翻转等于一次旋转

实现

写法一

写法二

复杂度分析

思考题

相似题目

分类题单