IT评测·应用市场-qidao123.com技术社区

标题: LeetCode 热题 100_旋转图像（20_48_中等_C++）（原地旋转；翻转） [打印本页]

---

作者: 张春    时间: 2024-12-6 04:26
标题: 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.length
1 <= n <= 20
-1000 <= matrix[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(N2）其中 N 是 matrix 的边长。我们需要对矩阵每一个位置进行移动
② 空间复杂度：O(1)。为原地旋转。
思路二（翻转）：

1、先将矩阵进行水平翻转（上下的翻转），再根据主对角线翻转。
注：这里你可以用你的手机模仿一下 水平翻转和 根据主对角线翻转的过程。
（扩展一下旋转180°，那我们可以上下翻转再左右翻转。）
2、复杂度分析
① 时间复杂度：O(N2)，其中 N 是 matrix 的边长。对于每一次翻转操作，我们都需要枚举矩阵中一半的元素。
② 空间复杂度：O(1)。为原地翻转得到的原地旋转。
代码实现（思路一（原地旋转））：

1. #include<iostream>
2. #include<vector>
3. using namespace std;
4. //思路一（原地旋转）
5. void rotate1(vector<vector<int>>& matrix) {
6.         int matrix_len=matrix.size();
7.         //当前数据还未进行处理的长度
8.         int now_len=matrix.size();
9.         //k代表从外向内的每一层（从0开始）
10.         int k=0;
11.        
12.         //从外圈开始逐层向内，一层while旋转最外边一层
13.         while(now_len>1){
14.                 //将最外层元素移动到对应位置
15.                 //注意for循环的结束条件，例：matrix[0][end] =matrix[0][begin]，在第一次时matrix[0][end]已经移动
16.                 for(int i=k;i<matrix.size()-1-k;i++){
17.                         //一次for循环移动四个元素
18.                         //拿出一个元素，剩余元素可依次移动
19.                         int tmp=matrix[k][i];
20.                         matrix[k][i]=matrix[(matrix_len-1)-i][k];
21.                         matrix[(matrix_len-1)-i][k]=matrix[(matrix_len-1)-k][(matrix_len-1)-i];
22.                         matrix[(matrix_len-1)-k][(matrix_len-1)-i]=matrix[i][(matrix_len-1)-k];
23.                         matrix[i][(matrix_len-1)-k]=tmp;                       
24.                 }
25.                 //减小一圈，长宽的长度-2
26.                 now_len-=2;
27.                 ++k;
28.         }
29. }
31. int main(){
32.         vector<vector<int>> matrix={{5,1,9,11},{2,4,8,10},{13,3,6,7},{15,14,12,16}};
33.         rotate1(matrix);
34.        
35.         for(const auto i:matrix){
36.                 for(const auto j:i){
37.                         cout<<j<<"\t";
38.                 }
39.                 cout<<endl;
40.         }
41.        
42.         return 0;
43. }

复制代码

代码实现（思路二（翻转））：

1. #include<iostream>
2. #include<vector>
3. using namespace std;
4. //思路二（翻转）
5. void rotate2(vector<vector<int>>& matrix) {
6.         //水平翻转
7.         for(int row=0;row<matrix.size()/2;++row){
8.                 for(int column=0;column<matrix.size();++column){
9.                         swap(matrix[row][column],matrix[matrix.size()-row-1][column]);
10.                 }
11.         }
12.         //根据主对角线翻转
13.         for(int row=0;row<matrix.size();++row){
14.                 for(int column=0;column<row;++column){
15.                         swap(matrix[row][column],matrix[column][row]);
16.                 }
17.         }
18.        
19. }

复制代码

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

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 IT评测·应用市场-qidao123.com技术社区 (https://dis.qidao123.com/)

Powered by Discuz! X3.4