【LeetCode每天一题】Rotate Image(旋转矩阵)

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, 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]
]
思路

---

　　题目要求我们只能再本地进行旋转，不能设置辅助空间。这道题在最开始做的时候，我先在草稿纸上画出交换的过程，然后从中找出规律。发现首先对于循环次数，当n是基数的时候，最里面的一层只有一个元素，不用进行旋转，所以循环的次数应该是 start < len(nums)//2.另外在元素交换的规律上，每一列有几个元素，我们就循环几次。意思是每一次循环交换的是将所有相应位置的元素进行交换。
　　时间复杂度为O(mlogm)， 其中m为矩阵一行的长度。空间复杂度为O(1)。
图解步骤

---

解决代码

---

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 l in range(n // 2):         # 循环条件
            r = n  -1-l                     # 右边开始的位置
            for p in range(l, r):      # 每一层循环次数
                q = n -1- p             # 每一次循环交换时底部元素的小标
                cache = matrix[l][p]      # 对元素进行交换。
                matrix[l][p] = matrix[q][l]
                matrix[q][l] = matrix[r][q]
                matrix[r][q] = matrix[p][r]
                matrix[p][r] = cache