LeetCode 热题 100_旋转图像（20_48_中等_C++）（原地旋转；翻转）
标题形貌：给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 利用另一个矩阵来旋转图像。
输入输出样例：
示例 1：
https://i-blog.csdnimg.cn/direct/d07037d501494599a2286dee0d9460ce.png
输入：matrix = [,,]
输出：[,,]
示例 2：
https://i-blog.csdnimg.cn/direct/07eea033d5ee40d395df42bef3b8f1fb.png
输入：matrix = [,,,]
输出：[,,,]
提示：
n== matrix.length == matrix.length
1 <= n <= 20
-1000 <= matrix <= 1000
题解：
解题思路：
思路一（原地旋转）：
1、标题要我们求旋转图像（顺时针旋转 90 度）
我们先观察规律：
例：
输入：matrix = [,,,]
输出：[,,,]
元素的位置变化：
5：00->03 1：01->03 9：02->23 11：03->33
2：10->02 4：11->12 8：12->22 10：13->32
我们会发现：
旋转前元素的行 + 旋转后元素的列 = 3（也就是边长n-1）
旋转前元素的列 = 旋转后元素的行
2、标题还要求必须在 原地 旋转图像，那我们可以先对一个元素位置进行旋转。
让5从00->03,11从03->33,16从33->30,15从30->00
https://i-blog.csdnimg.cn/direct/454693551c58493fab0c4627e328e4c3.png
① 转换成赋值语句（00等为下标伪代码）：这里可以将5拿出，以5的位置开始依次进行移位00=30 ; 30=33 ; 33=03 ; 03=拿出来的5。
② 拿出1，以1的位置开始依次进行移位01=20 20=32 32=13 13=拿出来的1。
③ 然后重复上述过程，直到旋转完最外圈的元素。
④ 再从外圈向内内圈依次进行上述旋转过程，直到每个元素的位置都旋转完成为止。
注意：外层到内层每层开始旋转的位置：…（内层的旋转图像是从4开始）
3、复杂度分析：
① 时间复杂度：O(N2）其中 N 是 matrix 的边长。我们需要对矩阵每一个位置进行移动
② 空间复杂度：O(1)。为原地旋转。
思路二（翻转）：
1、先将矩阵进行水平翻转（上下的翻转），再根据主对角线翻转。
注：这里你可以用你的手机模仿一下 水平翻转和 根据主对角线翻转的过程。
（扩展一下旋转180°，那我们可以上下翻转再左右翻转。）
2、复杂度分析
① 时间复杂度：O(N2)，其中 N 是 matrix 的边长。对于每一次翻转操作，我们都需要枚举矩阵中一半的元素。
② 空间复杂度：O(1)。为原地翻转得到的原地旋转。
代码实现（思路一（原地旋转））：
#include<iostream>
#include<vector>
using namespace std;
//思路一（原地旋转）
void rotate1(vector<vector<int>>& matrix) {
int matrix_len=matrix.size();
//当前数据还未进行处理的长度
int now_len=matrix.size();
//k代表从外向内的每一层（从0开始）
int k=0;
//从外圈开始逐层向内，一层while旋转最外边一层
while(now_len>1){
//将最外层元素移动到对应位置
//注意for循环的结束条件，例：matrix =matrix，在第一次时matrix已经移动
for(int i=k;i<matrix.size()-1-k;i++){
//一次for循环移动四个元素
//拿出一个元素，剩余元素可依次移动
int tmp=matrix;
matrix=matrix[(matrix_len-1)-i];
matrix[(matrix_len-1)-i]=matrix[(matrix_len-1)-k][(matrix_len-1)-i];
matrix[(matrix_len-1)-k][(matrix_len-1)-i]=matrix[(matrix_len-1)-k];
matrix[(matrix_len-1)-k]=tmp;
}
//减小一圈，长宽的长度-2
now_len-=2;
++k;
}
}
int main(){
vector<vector<int>> matrix={{5,1,9,11},{2,4,8,10},{13,3,6,7},{15,14,12,16}};
rotate1(matrix);
for(const auto i:matrix){
for(const auto j:i){
cout<<j<<"\t";
}
cout<<endl;
}
return 0;
}
代码实现（思路二（翻转））：
#include<iostream>
#include<vector>
using namespace std;
//思路二（翻转）
void rotate2(vector<vector<int>>& matrix) {
//水平翻转
for(int row=0;row<matrix.size()/2;++row){
for(int column=0;column<matrix.size();++column){
swap(matrix,matrix);
}
}
//根据主对角线翻转
for(int row=0;row<matrix.size();++row){
for(int column=0;column<row;++column){
swap(matrix,matrix);
}
}
}
LeetCode 热题 100_旋转图像（20_48)原题链接
欢迎大家和我沟通交换(✿◠‿◠)
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]