当前位置：首页 > backend >正文

L39.【LeetCode题解】面试题 01.07. 旋转矩阵(四种方法)

backend 2025/5/3 13:31:51

1.题目

2.分析

方法1:先转置再按每行反向存储

代码

提交结果

方法2:原矩阵从下往上遍历,新矩阵从左向右尾插

代码

提交结果

编辑

方法3:按行翻转后再将矩阵对称

代码

提交结果

按行翻转的其他做法

代码

提交结果

方法4:使用旋转向量辅助解决

数学推导

代码

准备代码

完整代码

精简版代码(从上方代码化简而来)

提交结果

1.题目

https://leetcode.cn/problems/rotate-matrix-lcci/description/

给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。

不占用额外内存空间能否做到？

示例 1：
给定 matrix = 
[[1,2,3],[4,5,6],[7,8,9]
],原地旋转输入矩阵，使其变为:
[[7,4,1],[8,5,2],[9,6,3]
]
示例 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]
]
注意：本题与主站 48 题相同：48. 旋转图像 - 力扣（LeetCode）

2.分析

方法1:先转置再按每行反向存储

先转置再按每行反向存储

代码

class Solution {
public:void rotate(vector<vector<int>>& matrix)//非转置矩阵{int N=matrix.size();vector<vector<int>> matrix1,matrix2;for (int col=0;col<N;col++)//先转置{vector<int> line;for (int row=0;row<N;row++){line.push_back(matrix[row][col]);}matrix1.push_back(line);}for (int row=0;row<N;row++)//反向存储{vector<int> line;for (int col=N-1;col>=0;col--){line.push_back(matrix1[row][col]);}matrix2.push_back(line);}matrix=matrix2;}
};

时间复杂度: $O(N)$ (若精确计算,为 $O(2N)$ )

提交结果

方法2:原矩阵从下往上遍历,新矩阵从左向右尾插

代码

class Solution {
public:void rotate(vector<vector<int>>& matrix)//非转置矩阵{int N=matrix.size();vector<vector<int>> tmp;for (int col=0;col<N;col++)//先转置{vector<int> line;for (int row=N-1;row>=0;row--){line.push_back(matrix[row][col]);}tmp.push_back(line);}matrix=tmp;}
};

时间复杂度: $O(N)$

提交结果

方法3:按行翻转后再将矩阵对称

直接引用LeetCode官方的分析图:

注:这个水平翻转其实镜像对称

根据主对角线翻转其实是转置,也是关于中心点对称:

代码

class Solution {
public:void rotate(vector<vector<int>>& matrix)//非转置矩阵{int N=matrix.size();for (int col=0;col<=N/2-1;col++)//按行翻转swap(matrix[col],matrix[N-col-1]);//直接交换行索引,不用交换每个元素for (int row=0;row<N;row++)//将矩阵对称for (int col=0;col<row;col++)swap(matrix[row][col],matrix[col][row]);}
};

注:将矩阵对称时,注意只需要对称上三角的元素(特征: col<row)

时间复杂度: $O(1)$

提交结果

按行翻转的其他做法

利用矩阵相乘,按行翻转

方法:左乘一个矩阵

例如矩阵 $\begin{bmatrix} 1&2& 3 \\ 4&5&6\\ 7&8&9 \end{bmatrix}$ :左乘一个 $\begin{bmatrix} 0&0&1 \\ 0&1&0 \\ 1&0&0 \end{bmatrix}$ ,则有以下式子: $\begin{bmatrix} 0&0&1 \\ 0&1&0 \\ 1&0&0 \end{bmatrix}\cdot \begin{bmatrix} 1&2& 3 \\ 4&5&6\\ 7&8&9 \end{bmatrix}=\begin{bmatrix} 7&8& 9 \\ 4&5&6\\ 1&2&3 \end{bmatrix}$

如果对于一个N*N的矩阵,对其进行按行翻转,可以左乘矩阵 $\begin{bmatrix} 0&0&0&0&...&0&1 \\ 0&0&0&0&...&1&0 \\ ..&...&...&...&...&...&...\\0&1&0&0&...&0&0\\1&0&0&0&...&0&0\end{bmatrix}$

代码遵循矩阵的乘法规则进行处理(注:和0相乘没有意义)

代码

class Solution {
public:void rotate(vector<vector<int>>& matrix)//非转置矩阵{int N=matrix.size();vector<vector<int>> tmp;for (int row=0;row<N;row++){vector<int> line;for (int col=0;col<N;col++){//第row行和第col行的对应元素相乘int sum=0;for (int index=0;index<N;index++){if (index+row==N-1)//如果满足条件,左乘的矩阵的第sum+=matrix[index][col];}line.push_back(sum);}tmp.push_back(line);}matrix=tmp;   for (int row=0;row<N;row++)//对称矩阵for (int col=0;col<row;col++)swap(matrix[row][col],matrix[col][row]);}
};

提交结果

方法4:使用旋转向量辅助解决

旋转矩阵实际上可以看做绕矩阵的右下角作顺时针旋转90°,如下图:

将旋转前后的矩阵拼在一起,看看有什么规律:

数学推导

带上坐标后:

看看旋转前后对应元素的坐标值的规律:

$\vec{a}=(1-2,0-2)=(-1,-2) \quad \vec{b}=(0-2,4-3)=(-2,1)$

$\vec{a}=(0-2,1-2)=(-2,-1) \quad \vec{b}=(1-2,5-3)=(-1,2)$

$\vec{a}=(2-2,0-2)=(0,-2) \quad \vec{b}=(0-2,3-3)=(-2,0)$

发现无论是什么元素选择, $\vec{a}$ 和 $\vec{b}$ 都是垂直的,换句话说 $\vec{a}\cdot \vec{b}=\vec{0}$ ( $\vec{a}$ 和 $\vec{b}$ 的起始点分别为旋转前矩阵的右下角和旋转后矩阵的做下角),

而且 $\vec{a}$ 和 $\vec{b}$ 的横纵坐标是有规律的:

$\vec{a}_x=-\vec{b}_y$

$\vec{a}_y=\vec{b}_x$

本质上 $\vec{a}$ 通过右乘一个矩阵 $\begin{bmatrix} 0&-1 \\ 1&0 \end{bmatrix}$ 得到 $\vec{b}$ ,矩阵的作用效果是使 $\vec{a}$ 顺时针旋转90°

可由此来计算旋转后各个元素的坐标

注: $\begin{bmatrix} 0&-1 \\ 1&0 \end{bmatrix}$ 其实是 $\begin{bmatrix} sin\varphi &-cos\varphi \\ cos\varphi&sin\varphi \end{bmatrix}$ 中 $\varphi=90^{\circ}$ 的情况

代码

设 $\vec{a}$ 和 $\vec{b}$ 的起始点和终止点分别为A、B、C和D,则 A_x、A_y、B_x、B_y、C_x、C_y、D_x和D_y分别为它们的横纵坐标

A和C的坐标是固定的,对于N*N的方阵而言,

A_x=N-1

A_y=N-1

C_x=N

C_y=N-1

准备代码

int N=matrix.size();
int arr[N][N];
int A_x=N-1,A_y=N-1,B_x,B_y,C_x=N-1,C_y=N,D_x,D_y;

完整代码

class Solution {
public:void rotate(vector<vector<int>>& matrix){vector<vector<int>> tmp;const int N=matrix.size();int arr[100][100];int A_x=N-1,A_y=N-1,B_x,B_y,C_x=N-1,C_y=N,D_x,D_y;for (B_x=0;B_x<N;B_x++){for (B_y=0;B_y<N;B_y++){int a_x=B_x-A_x;int a_y=B_y-A_y;int b_x=a_y;int b_y=-a_x;//b_x==D_x-C_x,b_y==D_y-C_yD_x=b_x+C_x;D_y=b_y+C_y;arr[D_x][D_y-N]=matrix[B_x][B_y];}}for (int i=0;i<N;i++){vector<int> line;for (int j=0;j<N;j++)line.push_back(arr[i][j]);tmp.push_back(line);}matrix=tmp;}
};

精简版代码(从上方代码化简而来)

class Solution {
public:void rotate(vector<vector<int>>& matrix){vector<vector<int>> tmp;const int N=matrix.size();int arr[100][100];for (int B_x=0;B_x<N;B_x++){for (int B_y=0;B_y<N;B_y++)arr[B_y][N-1-B_x]=matrix[B_x][B_y];}for (int i=0;i<N;i++){vector<int> line;for (int j=0;j<N;j++)line.push_back(arr[i][j]);tmp.push_back(line);}matrix=tmp;}
};