旋转图像

发表于 | 分类于 | | 阅读次数:

旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像，将图像顺时针旋转 90 度。必须在原地旋转图像，这意味着需要直接修改输入的二维矩阵，而不能使用另一个矩阵来旋转图像。

图像旋转

leetcode-48

方法一

分析

通过找规律的方式能够得到旋转前后元素之间的映射关系，但是严格来说这是一道几何题，主要考察了空间变换的知识。

图像旋转的效果如图1所示

图1

其旋转过程其实包括了两部分，第一步绕原点顺时针旋转90°，第二步沿原y轴右移n - 1
图2

这两步的变换矩阵可以写出来

$$
\begin{bmatrix}
0 & 1 & 0 \\
-1 & 0 & n-1 \\
0 & 0 & 1 \\
\end{bmatrix}
$$

进一步可以得到坐标变换公式，代表原始位置的坐标变换后的新坐标

$$
\begin{bmatrix}
0 & 1 & 0 \\
-1 & 0 & n-1 \\
0 & 0 & 1 \\
\end{bmatrix}
\begin{bmatrix}
ori_x \\
ori_y \\
1 \\
\end{bmatrix}
=
\begin{bmatrix}
new_x \\
new_y \\
1 \\
\end{bmatrix}
$$

即

1
2
new_x = ori_y
new_y = n - 1 - ori_x

反向可以推出任意位置的新坐标是由哪一原始坐标得到的(方便写代码)

1
2
ori_x = n - new_y - 1
ori_y = new_x

于是我们通过坐标变换的方式得到了公式

代码

时间复杂度：O(n^2)
空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        if(n <= 1) return;

        for(int i = 0; i < n / 2; ++i){
            for(int j = i; j < n - i - 1; ++j){
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[n - 1 - j][i];
                matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];
                matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i];
                matrix[j][n - 1 - i] = tmp;
            }
        }
        return;
    }
};

方法二

solution2

代码

时间复杂度：O(n^2)
空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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]);
            }
        }
        
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < n / 2; ++j){
                swap(matrix[i][j], matrix[i][n - 1 - j]);
            }
        }
    }
};