LeetCode 热题 100_旋转图像（20_48_中等_C++）（原地旋转；翻转）

题目描述：

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 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]]

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

题解：

解题思路：

思路一（原地旋转）：

1、题目要我们求旋转图像（顺时针旋转 90 度）
我们先观察规律：
例：
输入：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]]
元素的位置变化：

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

① 转换成赋值语句（00等为下标伪代码）：这里可以将5拿出，以5的位置开始依次进行移位00=30 ; 30=33 ; 33=03 ; 03=拿出来的5。
② 拿出1，以1的位置开始依次进行移位01=20 20=32 32=13 13=拿出来的1。
③ 然后重复上述过程，直到旋转完最外圈的元素。
④ 再从外圈向内内圈依次进行上述旋转过程，直到每个元素的位置都旋转完成为止。
注意：外层到内层每层开始旋转的位置：[0,0][1,1][2,2]…（内层的旋转图像是从4开始）

3、复杂度分析：
① 时间复杂度：O(N²）其中 N 是 matrix 的边长。我们需要对矩阵每一个位置进行移动
② 空间复杂度：O(1)。为原地旋转。

思路二（翻转）：

1、先将矩阵进行水平翻转（上下的翻转），再根据主对角线翻转。
注：这里你可以用你的手机模拟一下 水平翻转和 根据主对角线翻转的过程。
（扩展一下旋转180°，那我们可以上下翻转再左右翻转。）

2、复杂度分析
① 时间复杂度：O(N²)，其中 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[0][end] =matrix[0][begin]，在第一次时matrix[0][end]已经移动 for(int i=k;i<matrix.size()-1-k;i++){//一次for循环移动四个元素 //拿出一个元素，剩余元素可依次移动 int tmp=matrix[k][i];matrix[k][i]=matrix[(matrix_len-1)-i][k];matrix[(matrix_len-1)-i][k]=matrix[(matrix_len-1)-k][(matrix_len-1)-i]; matrix[(matrix_len-1)-k][(matrix_len-1)-i]=matrix[i][(matrix_len-1)-k];matrix[i][(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[row][column],matrix[matrix.size()-row-1][column]);}} //根据主对角线翻转for(int row=0;row<matrix.size();++row){for(int column=0;column<row;++column){swap(matrix[row][column],matrix[column][row]);}}}

LeetCode 热题 100_旋转图像（20_48)原题链接
欢迎大家和我沟通交流(✿◠‿◠)