0048. 旋转图像

[utterances-bot]

0048. 旋转图像 | 算法通关手册

48. 旋转图像 # 标签：数组 难度：中等 题目大意 # 描述：给定一个 n * n 大小的二维矩阵（代表图像）matrix。 要求：将二维矩阵 matrix 顺时针旋转 90°。 说

https://algo.itcharge.cn/Solutions/0001-0099/rotate-image/

[charles2268]

致初学者：
思路2的代码如果没看懂，可以参考这个视频链接：https://www.youtube.com/watch?v=tFZPEpNtIsw&list=PLDWzcHf8iVS7-lhQ7olQhwTB2k-LrGUh-&index=5

[Derek-cny]

感谢 成功理解
class Solution(object):
def rotate(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: None Do not return anything, modify matrix in-place instead.
"""
n=len(matrix)
for i in range(n):
for j in range (i,n):
matrix[i][j],matrix[j][i]=matrix[j][i],matrix[i][j]
for i in range(n):
for j in range (n//2):
matrix[i][j],matrix[i][n-1-j]=matrix[i][n-1-j],matrix[i][j]
return matrix

[chiao666]

请问为啥这里不需要一个中间变量存储matrix[i][j]也可以正常运行

[kuso2006]

思路一基础思路不难，难的是后续能够写出来N+1，这玩意完全看运气
因为正常人思路都是横着遍历到头，然后再看第二行，这样很容易陷入到无底洞。我不知道怎么才能想到：横着走一半就停止，然后接着走下一行。只能看运气了

[h-jm98]

确实容易陷进去，不过n本身就分奇偶，仔细想想也能出来，就是费时间

[BigFlower666]

这里有规律的，遍历的这个小矩阵，旋转4次后 要覆盖大的矩阵

[kuso2006]

补充一下为什么思路一是玄学，做对的偶然性很大

思路一（数学关系 + 演绎）：

1. 画图观察下标变化情况，归纳新旧坐标映射：
   （i, j）-> (j, n-i-1)
2. 简单粗暴的做法，引入额外空矩阵，依据上述映射赋值，但是不符合题目限制
3. 不让使用额外空间，那参考排序里的做法，一般对策就是在原数据结构上交换元素。但是直接交换来的元素可能不在它应该在的位置，那就根据其原坐标计算该元素该在的下标，继续迭代上述过程直至收敛
4. 演绎一次发现，每次只能够收敛一圈（收敛四个元素）。如果你是按下标顺序遍历的话，能够覆盖矩阵的收敛，并且没有重复
5. 测试发现，两层循环的顺序不对！比如对于n=5的情况，应该是
   第一行遍历4个元素，第二行遍历2个元素，第三行遍历1个元素。
   你可以尝试更多，完全没有规律，即便有也很难归纳。
6. 查看了题解之后发现，正确解法不是按下标顺序遍历的，而是：

• 对于n=奇数，遍历其上三角
• 对于n=偶数，遍历其上1/4方阵
  步骤六是正确答案，但是完全没有逻辑，这就很没意思，玄学的玩意。95%的人会按照逻辑一步步演绎到步骤5，陷入其中，5%的幸运儿或许是碰巧或许是极强的洞察力演绎到了6。所以该题强烈不推荐这种演绎的思路，一个看运气的方案太扯了

[kuso2006]

思路二（数学关系 + 物理意义）：

1. 画图观察下标变化情况，归纳新旧坐标映射：
   （i, j）-> (j, n-i-1)
2. 对于数学表达敏锐一点能够发现，上述映射可以分为两步：
   (i, j) -> (j, i) -> (j, (n-1)-i)，其物理意义是

• 沿主对角线翻转
• 水平翻转
  Done!

思路二难点在于有这样的数学直觉，其实说白了也是看经验。现在越来越感觉，计算机刷题的本质就是在积攒经验，到不至于说是背题，而是背诵遇到过的各种关键点（比如常见的双指针，不常见的如本题）。
所以，想不到思路的新人朋友不必气馁，很正常，那些老鸟也是这样一路背过来的，并不是说他们就聪明多少，只是背的关键点多了，遇到题目从关键点数据库中抽出来应用就解决了，最典型的就是题解评论区中的那些奇淫巧技，很多时候你觉得没道理啊，作者自己也讲不出为什么一步步推到出这种思路，因为算法题就不是推到出来的解法，「全是背的关键点+应用啊朋友们」

[banfenfen]

是不是有点写错了，文字写【水平翻转】但代码是竖直翻转。要么先转置再水平翻转，要么先竖直翻转再转置