#48 Rotate Image——Top 100 Liked Questions

Bertha 。 2022-01-30 03:15 182阅读 0赞

You are given an *n* x *n* 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

**Note:**

You have to rotate the image [**in-place**][in-place], which means you have to modify the input 2D matrix directly. **DO NOT** allocate another 2D matrix and do the rotation.

**Example 1:**

Given input matrix = 
    [
      [1,2,3],
      [4,5,6],
      [7,8,9]
    ],
    
    rotate the input matrix in-place such that it becomes:
    [
      [7,4,1],
      [8,5,2],
      [9,6,3]
    ]

**Example 2:**

Given input matrix =
    [
      [ 5, 1, 9,11],
      [ 2, 4, 8,10],
      [13, 3, 6, 7],
      [15,14,12,16]
    ], 
    
    rotate the input matrix in-place such that it becomes:
    [
      [15,13, 2, 5],
      [14, 3, 4, 1],
      [12, 6, 8, 9],
      [16, 7,10,11]
    ]

> """
> 
> 第一次：通过找规律，发现(i, j)-->(j, n-1-i)，但是直接交换是有错的
> 
> 第二次：网上参考：先以对角线为轴翻转，再以x轴中线翻转，蓝色数字是翻转轴，可以通过找规律发现i和j的范围以及交换的zuobao（[https://www.cnblogs.com/grandyang/p/4389572.html][https_www.cnblogs.com_grandyang_p_4389572.html]）
> 
> ![20190517200045294.png][]
> 
> """
> 
>     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(n - i - 1):
>                     tmp = matrix[i][j]
>                     matrix[i][j] = matrix[n - 1 - j][n - 1 - i]
>                     matrix[n - 1 - j][n - 1 - i] = tmp
>             
>             for i in range(n // 2):
>                 for j in range(n):
>                     tmp = matrix[i][j]
>                     matrix[i][j] = matrix[n - 1 - i][j]
>                     matrix[n - 1 - i][j] = tmp
> 
> """
> 
> Runtime: 20 ms, faster than 98.51% of Python online submissions for Rotate Image.
> 
> Memory Usage: 11.8 MB, less than 30.58% of Python online submissions for Rotate Image.
> 
> """

[in-place]: https://en.wikipedia.org/wiki/In-place_algorithm
[https_www.cnblogs.com_grandyang_p_4389572.html]: https://www.cnblogs.com/grandyang/p/4389572.html
[20190517200045294.png]: /images/20220130/bca524c876fa4b438fd061d925acd699.png