文章目录
这道题解法非常多，另外此题同 https://leetcode-cn.com/problems/rotate-matrix-lcci/ 面试题 01.07. 旋转矩阵
映射关系 AC
假设矩阵A是原本的矩阵，B是旋转后的矩阵，n是矩阵行数
那么A、B中元素有如下映射关系
A
[
i
]
[
j
]
=
B
[
j
]
[
n
−
i
−
1
]
A[i][j] = B[j][n-i-1]
A[i][j]=B[j][n−i−1]并且这个映射是单一映射，那现在就好办了，我们只要从A矩阵按照这个映射关系构造B矩阵就行
由于题目要求不能用额外的空间，那么我们使用循环来完成映射，假设A是4X4的矩阵，现在
A
[
0
]
[
0
]
A[0][0]
A[0][0]需要映射
如果我们直接修改A，那么
A
[
0
]
[
3
]
A[0][3]
A[0][3]的元素会缺失，无法完成答案，所以我们需要继续执行映射，直到回到0,0本身
如此：
(
0
,
0
)
⇒
(
0
,
3
)
⇒
(
3
,
3
)
⇒
(
3
,
0
)
⇒
(
0
,
0
)
(0,0) \Rightarrow (0,3) \Rightarrow (3,3) \Rightarrow (3,0) \Rightarrow (0,0)
(0,0)⇒(0,3)⇒(3,3)⇒(3,0)⇒(0,0)，这个映射关系是长度为
n
n
n的环
如图所示
为了描述方便，我们称上述这样的交换为循环映射
下面我们可以按照这个思路编写代码
实际上整个矩阵是被一圈一圈元素组成的，我们只需要交换每一圈的元素即可
考虑到4X4的矩阵A，一共是由两圈元素构成
对于第一圈，我们只需要对前n - 1个元素完成循环映射即可，如图所示
接下来我们就可以写出代码了
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
n = len(matrix)
# 记录圈数，n==2的时候是特殊条件，只由1圈围成
if n == 2:
cnt = 1
else:
cnt = n-2 if n%2==0 else n-1
# 对于矩阵的每一圈
for i in range(cnt):
# 每一圈最后一个元素不需要交换，同时之前交换过的元素也不需要交换
for j in range(i,n - i - 1):
# 起点
sx,sy = i,j
# 映射关系
nx,ny = j,n-i-1
last = matrix[sx][sy]
while (nx,ny) != (sx,sy):
matrix[nx][ny],last = last,matrix[nx][ny]
# 更新下一个坐标
nx,ny = ny,n-nx-1
# 更新起始元素
matrix[sx][sy] = last
这个思路很像 https://leetcode-cn.com/problems/rotate-array/ 189. 旋转数组里面的一个解法
题解
整理一下别人的题解
借用辅助空间
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
// C++ 这里的 = 拷贝是值拷贝，会得到一个新的数组
auto matrix_new = matrix;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
matrix_new[j][n - i - 1] = matrix[i][j];
}
}
// 这里也是值拷贝
matrix = matrix_new;
}
};
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/rotate-image/solution/xuan-zhuan-tu-xiang-by-leetcode-solution-vu3m/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
原地旋转
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
for (int i = 0; i < n / 2; ++i) {
for (int j = 0; j < (n + 1) / 2; ++j) {
int temp = matrix[i][j];
matrix[i][j] = matrix[n - j - 1][i];
matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
matrix[j][n - i - 1] = temp;
}
}
}
};
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/rotate-image/solution/xuan-zhuan-tu-xiang-by-leetcode-solution-vu3m/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
和映射一样的思路，只不过这里直接写出来了
对角线反转
利用反转的性质
Amazing！！！
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
n = len(matrix)
# 水平翻转
for i in range(n // 2):
for j in range(n):
matrix[i][j], matrix[n - i - 1][j] = matrix[n - i - 1][j], matrix[i][j]
# 主对角线翻转
for i in range(n):
for j in range(i):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/rotate-image/solution/xuan-zhuan-tu-xiang-by-leetcode-solution-vu3m/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。