旋转矩阵

难度: Medium

给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。

不占用额外内存空间能否做到？

示例 1:

给定 matrix = 
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],

原地旋转输入矩阵，使其变为:
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]

示例 2:

给定 matrix =
[
  [ 5, 1, 9,11],
  [ 2, 4, 8,10],
  [13, 3, 6, 7],
  [15,14,12,16]
], 

原地旋转输入矩阵，使其变为:
[
  [15,13, 2, 5],
  [14, 3, 4, 1],
  [12, 6, 8, 9],
  [16, 7,10,11]
]

注意：本题与主站 48 题相同：https://leetcode-cn.com/problems/rotate-image/

Submission

运行时间: 19 ms

内存: 16.0 MB

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

Explain

该题解采用了一种原地旋转的方法。首先设定循环的层数为 n//2，对于每一层，使用一个嵌套的循环来处理这一层的元素。旋转过程涉及到四个相关联的元素，这四个元素分别位于矩阵的四个不同的‘角’位置。对于每一对(i, j)，进行以下转换： 1. 保存 matrix[i][j] 的值到临时变量 tmp。 2. 将 matrix[n-1-j][i] 的值移动到 matrix[i][j]。 3. 将 matrix[n-1-i][n-1-j] 的值移动到 matrix[n-1-j][i]。 4. 将 matrix[j][n-1-i] 的值移动到 matrix[n-1-i][n-1-j]。 5. 将 tmp (原 matrix[i][j] 的值) 移动到 matrix[j][n-1-i]。这个过程会使得每个元素被旋转到正确的位置，并且只使用一个额外变量，满足原地旋转的要求。

时间复杂度: O(N^2)

空间复杂度: O(1)

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        n = len(matrix)  # 获取矩阵的维度
        for i in range(n//2):  # 对于每一层
            for j in range((n+1)//2):  # 对于每一层中的元素
                tmp = matrix[i][j]  # 保存当前元素
                matrix[i][j] = matrix[n-1-j][i]  # 进行旋转
                matrix[n-1-j][i] = matrix[n-1-i][n-1-j]  # 进行旋转
                matrix[n-1-i][n-1-j] = matrix[j][n-1-i]  # 进行旋转
                matrix[j][n-1-i] = tmp  # 完成旋转

Explore

在旋转矩阵时选择`n//2`作为层数进行循环的原因是，对于一个n*n的矩阵，其旋转可以视为从最外层开始逐层向内部进行。每一层都可以看作是一个环形结构，需要整体旋转。由于每次处理一层时都在同时处理该层的上下两边，因此只需要遍历到矩阵中间的层即可。对于奇数n，中间的单个元素不需要移动；对于偶数n，最内层已经是最后的两行两列在之前的层已经处理完毕。因此，`n//2`能够确保所有层都被正确处理。

在处理每一层的元素时，使用`(n+1)//2`来确定每层的迭代次数是为了确保在每一层中的每个元素都被处理到，尤其是当n为奇数时。这是因为在每一层中，我们需要处理从左到右的元素，并且这些元素在旋转后会移动到不同的位置。当矩阵的维度为奇数时，中间的列需要额外的处理以确保中心元素也被旋转到正确的位置。因此，`(n+1)//2`可以保证在所有情况下，每层的元素都被充分旋转。

在进行原地旋转时，变量`tmp`的使用确保了所有元素的正确交换。这种方法通过保存一个元素的值到`tmp`，然后依次将其它三个相关联的元素移到正确的位置，最后将保存在`tmp`中的值移到最后一个位置。这个过程形成了一个完整的循环，确保了四个元素都被旋转到了正确的位置。由于每个元素只被处理一次，并且每次处理都包括了所有相关联的四个位置，因此不会出现错过某些元素或未被正确旋转的情况。