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

[rui-ao]

请问为啥这里不需要一个中间变量存储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]

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

[ivyinautumn]

用嵌套列表推导式

class Solution(object):
    def rotate(self, matrix: List[int]) -> None:
        '''
        :type matrix: List[List[int]]
        :rtype: None Do not return anything, modify matrix in-place instead.
        '''
        n = len(matrix)
        matrix[:] = [[matrix[j][i] for j in range(n-1, -1, -1)] for i in range(n)]

[D-ing-jun]

matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
n = len(matrix)
res = [[0] * n for _ in range(n)]

for i in range(n-1, -1, -1):
    for j in range(-1,n):
        res[j][n-i-1] = matrix[i][j]


print(res)

[Wan-Yifei]

不怕诸位笑话，我一个老码工居然想了一个小时……
方法一说起来简单实际上推导出n+1很玄学。我换了个思路，把矩阵类比视为一圈一圈的正方形进行处理。对于每一圈只用推导其四个角的数值交换情况。举例来说最外圈的正方形四个角、依次为A/B/C/D四个点，那旋转九十度的情况就是：A->B, B->C, C->D, D->A, 一个点连续转4次就会回到原位。可以轻易推导出对应的坐标交换关系：(i,j）-> (j, n-1-i) -> (n-1-i, n-1-j) -> (n-1-j, i) -> (i, j)。所以只需要遍历矩阵拿到点的坐标按上面的顺序交换就好。因为我们是一圈一圈处理，所以只需要遍历圈数n//2就够了，如果边长是奇数正中心的点刚好就不会动不用管。而对于每一圈（一个正方形）我们只用再遍历其一条边就能拿到其他三条边的所有坐标，能容易推出边长是n-1-i。例如一个3*3矩阵，对第一圈（i=0）, 其边长为3-i-0 = 3。其实最后遍历的区域是以正方形的一条边为底，以正方形中心为顶点连接正方形两个角形成的等腰三角形，只占矩阵的1/4。
代码如下：

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        n = len(matrix)
        if n == 0:
            return
        for i in range(n//2):
            for j in range(i, n-1-i):
                matrix[i][j], matrix[j][n-i-1], matrix[n-1-i][n-1-j], matrix[n-1-j][i] = \
                matrix[n-1-j][i], matrix[i][j], matrix[j][n-i-1], matrix[n-1-i][n-1-j]

[m202321666]

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        n = len(matrix)
        for i in range (0,n):
            for j in range(i,n):
                 matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
            matrix[i].reverse()
        return matrix

[tm-chen-214]

题目的意思就是将一个二维数组进行水平翻转，从实现角度来看就是将一个下标的元素移动到另一个下标，先尝试找一下规律：
一个4 X 4的矩阵的下标应该是这样：

00 01 02 03
10 11 12 13
20 21 22 23
30 31 32 33

翻转之后原来下标的新位置应该是这样：

30 20 10 00
31 21 11 01
32 22 12 02
33 23 13 03

来看一下规律，以第一个点为例，移动过程如下：

00→03→33→30→00

第一个点 00 的元素将会移动到原来 03 的位置，03 的元素移动到 33 的位置，33到 30，然后 30到 00 的位置，完成一个循环，翻转完成。将下标的行记作 i，列记作 j。i 的移动过程变化是 0→0→3→3→0，j 的变化过程是 0→3→3→0→0。规律并不明显，再看一个点，第二个点的变化：

01→13→32→20→01


当前i　当前j　目标i　目标j →　当前i　目标i 　当前j　目标j　→　目标i 当前j　 目标j 当前i
0　　 　1 　　　1 　　3 　　　　0 　　1 　　　1 　　　3　　　1 　　1 　　　　3 　　0
1　　 　3 　　　3 　　2　 　　　1 　　3 　　　3 　　　2　　　3 　　3 　　　　2 　　1
3　　 　2 　　　2 　　0 　　　　3 　　2 　　　2 　　　1　　　2 　　2 　　　　1 　　2
2　　　 0 　　　0 　　1 　　　　2 　　0 　　　0 　　　0　　　0 　　0 　　　　0 　　3

单独看并没有发现规律，交替一下来看，可以很容易发现规律。目标点的i就是当前的j，即当前元素的列号就是目标位置的行号；目标位置的j与当前位置的i呈现反序列额关系，即j = n - 1 - i。将这个规律带入其他点运算一下发现都满足，因此代码可以这样写(Python还不会，用C++代替一下)：

for(int i = 0; i < n; i++)
{
     for(int j = i; j < n - i - 1; j++)
     {
          int temp = arr[n - 1 - j][i];
          arr[n - 1 - j][i] = arr[n - 1 - i][n - 1 - j];
          arr[n - 1 - i][n - 1 - j] = arr[j][n - 1 - i];
          arr[j][n - 1 - i] = arr[i][j];
          arr[i][j] = temp ;
     }
}

这样计算就相当于从外向内逐个圈的翻转，因此内层循环的次数要逐个减少，还要注意内层循环的 n - i 还要减 1，最开始写代码没有减 1 发现翻转出来完全不对，因为第一行的第一个点移动到了最后一列，第一行最后一个列移动到了最后一列的最后一行，以此类推，所以每一圈移动的次数为当前的元素个数减一。
第一次提交，不知道讲明白没有，请多指正。

[tm-chen-214]

当前i　当前j　目标i　目标j →　当前i　目标i 　当前j　目标j　→　目标i 当前j　 目标j 当前i
0　　 　1 　　　1 　　3 　　　　0 　　1 　　　1 　　　3　　　1 　　1 　　　　3 　　0
1　　 　3 　　　3 　　2　 　　　1 　　3 　　　3 　　　2　　　3 　　3 　　　　2 　　1
3　　 　2 　　　2 　　0 　　　　3 　　2 　　　2 　　　1　　　2 　　2 　　　　1 　　2
2　　　 0 　　　0 　　1 　　　　2 　　0 　　　0 　　　0　　　0 　　0 　　　　0 　　3
上面的格式混乱了，更正一下