LeetCode in Python 48. Rotate Image/Matrix (旋转图像/矩阵)

旋转图像/矩阵的重点是寻找旋转前后对应位置的坐标关系。

示例：

图1 旋转图像/矩阵的输入输出示意图 

代码： 

class Solution:
    def rotate(self, matrix):
        n = len(matrix)
        for i in range(n // 2):
            for j in range(i, n - 1 - i):
                topleft = 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] = topleft

解释：

1）外层循环控制需要转的大圈圈数，内层循环控制每一圈需要转的小圈圈数，大小圈数的解释见图2，例如n=4，需要循环n // 2 = 2大圈，其中黄色循环箭头为第一大圈，绿色循环箭头为第二大圈。对于第一大圈，5->11->16->15->5为一小圈，同理1->10->12->13->1、9->7->14->2->9各为一小圈。

2）对于如何确定旋转前后位置坐标的对应关系，笔者是通过先确定再确定内层的方法，例如对于第一圈，固定i=0，然后观察大圈位置变化确定对应关系，接着改变i，观察内层圈数与i的对应关系进而修改对应坐标变化，如若先固定外层大圈循环，位置坐标变化应为：

matrix[0][j] = matrix[n - 1 - j][0]
matrix[n - 1 - j][0] = matrix[n - 1 - 0][n - 1 - j]
matrix[n - 1 - 0][n - 1 - j] = matrix[j][n - 1 - 0]
matrix[j][n - 1 - 0] = topleft

接着改变圈数，进入内层大圈循环，修改坐标变化：

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] = topleft

3）为了使算法空间复杂度为O(1)，只需将每一次循环的左上角元素保存下来，接着采用逆向循环的顺序调整元素，最后将左上角元素归位即可，如此便无需重新开辟一个O() 空间来保存原始矩阵。

另外附上另一种实现方式：

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        l, r = 0, len(matrix) - 1
        while l < r:
            for i in range(r - l):
                top, bot = l, r
                topleft = matrix[top][l + i]
                matrix[top][l + i] = matrix[bot - i][l]
                matrix[bot - i][l] = matrix[bot][r - i]
                matrix[bot][r - i] = matrix[top + i][r]
                matrix[top + i][r] = topleft
            l += 1
            r -= 1