LeetCode20 - 旋转图像 | 很多时候不懂事

📝 题目描述

题目链接：旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

示例：

示例 1：

1 2	输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出：[[7,4,1],[8,5,2],[9,6,3]]

示例 2：

1 2	输入：matrix = [[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]]

提示：

n == matrix.length == matrix[i].length
1 <= n <= 20
-1000 <= matrix[i][j] <= 1000

💡 解题思路

方法一：原地旋转

仔细思考，对于一个 $n \times n$ 矩阵的任意位置 $[i,\ j]$ ，推断一下其在旋转后的坐标是 $[j,\ n - 1 - i]$ 。

对于矩阵的任意位置 $[i, j]$ ，深入思考：

第一次追踪： $[i,\ j] \ \Longrightarrow \ [j,\ n - 1 - i]$ ；

第二次追踪： $[j,\ n - 1 - i] \ \Longrightarrow \ [n - 1 - i,\ n - 1 - j]$ ；

第三次追踪： $[n - 1 - i,\ n - 1 - j] \ \Longrightarrow \ [n - 1 - j,\ i]$ ；

第四次追踪： $[n - 1 - j,\ i] \ \Longrightarrow \ [i,\ j]$ ；

不难发现四次追踪就回到了原位，继续思考，我们可以把矩阵分为原点对称的四块：

对于偶数行矩阵：

对于奇数行矩阵：

也就是说，我们只需对其中一块进行连续追踪旋转，直到回到初始坐标。

方法二：用翻转代替旋转

我们还可以另辟蹊径，用翻转操作代替旋转操作。我们还是以题目中的示例二：

$\begin{bmatrix} 5 & 1 & 9 & 11 \\ 2 & 4 & 8 & 10 \\ 13 & 3 & 6 & 7 \\ 15 & 14 & 12 & 16 \end{bmatrix}$

作为例子，先将其通过水平轴翻转得到：

$\begin{bmatrix} 5 & 1 & 9 & 11 \\ 2 & 4 & 8 & 10 \\ 13 & 3 & 6 & 7 \\ 15 & 14 & 12 & 16 \end{bmatrix}\xrightarrow{\text{水平翻转}} \begin{bmatrix} 15 & 14 & 12 & 16 \\ 13 & 3 & 6 & 7 \\ 2 & 4 & 8 & 10 \\ 5 & 1 & 9 & 11 \end{bmatrix}$

再根据主对角线翻转得到：

$\begin{bmatrix} 15 & 14 & 12 & 16 \\ 13 & 3 & 6 & 7 \\ 2 & 4 & 8 & 10 \\ 5 & 1 & 9 & 11 \end{bmatrix}\xrightarrow{\text{主对角线翻转}} \begin{bmatrix} 15 & 13 & 2 & 5 \\ 14 & 3 & 4 & 1 \\ 12 & 6 & 8 & 9 \\ 16 & 7 & 10 & 11 \end{bmatrix}$

就得到了答案。这是为什么呢？对于水平轴翻转而言，我们只需要枚举矩阵上半部分的元素，和下半部分的元素进行交换，即

$matrix[row][col]\xrightarrow{\text{水平轴翻转}}matrix[n-1-row][col]$

对于主对角线翻转而言，我们只需要枚举对角线左侧的元素，和右侧的元素进行交换，即

$matrix[row][col]\xrightarrow{\text{主对角线翻转}}matrix[col][row]$

两者联立影响：

$matrix[row][col]\xrightarrow{\text{水平轴翻转+主对角线翻转}}matrix[col][n-1-row]$

这和我们方法一中的式子是一样的。

🔧 代码实现

1、原地旋转

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        if (matrix.empty()) return;
        int n = matrix.size();
        // 四个一循环，所以分四块
        int row_max = n / 2, col_max = n / 2 + n % 2;
        // 遍历第一块，进行追踪交换即可
        for (int i = 0; i < row_max; i++) {
            for (int j = 0; j < col_max; j++) {
                // 记录起点
                int current_i = i, current_j = j;
                // 创建临时变量，保存中转值
                int value = matrix[i][j];
                do {
                    // 找到下一个要交换的位置
                    int next_i = current_j, next_j = n - 1 - current_i;
                    // 令其与中转值进行交换
                    swap(matrix[next_i][next_j], value);
                    // 更新当前位置
                    current_i = next_i, current_j = next_j;
                } while ((current_i != i) || (current_j != j));
            }
        }
    }
};

2、用翻转代替旋转

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        if (matrix.empty()) return;
        int n = matrix.size();

        // 水平翻转
        for (int i = 0; i < n / 2; i++) {
            for (int j = 0; j < n; j++) {
                swap(matrix[i][j], matrix[n - 1 -i][j]);
            }
        }
        
        // 主对角线翻转
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                swap(matrix[i][j], matrix[j][i]);
            }
        }

        // 主对角线翻转（另一种写法）
        // for (int i = 0; i < n; i++) {
        //     for (int j = 0; j < i; j++) {
        //         swap(matrix[i][j], matrix[j][i]);
        //     }
        // }
    }
};

📊 复杂度分析

1、原地旋转

时间复杂度： $O(N^2)$ ，其中 N 是 matrix 的边长。我们需要枚举的子矩阵大小为 $O(⌊\frac{n}{2}⌋×⌊\frac{n+1}{2}⌋)=O(N^2)$ 。
空间复杂度： $O(1)$ 。为原地旋转。

2、用翻转代替旋转

时间复杂度： $O(N^2)$ ，其中 N 是 matrix 的边长。对于每一次翻转操作，我们都需要枚举矩阵中一半的元素。
空间复杂度： $O(1)$ 。为原地翻转得到的原地旋转。

🎯 总结

核心思想：两种思路都不错，可对比“轮转数组”的写法。