48 Rotate Image

题目

Rotate Image

题解

digraph array_2d
{
	rankdir=LR

	node[shape=box]
	Top0[label="Top0/Left4"]
	Right0[label="Right0/Top4"]
	Bottom0[label="Bottom0/Right4"]
	Left0[label="Left0/Bottom4"]

	Top0 -> Right0
	Right0:e -> Bottom0:e
	Bottom0 -> Left0 -> Top0[constraint=false]

	edge[dir=none]
	Top0 -> Top1 -> Top2 -> Top3 -> Right0
	Left3 -> A1 -> A2 -> A3 -> Right1
	Left2 -> B1 -> B2 -> B3 -> Right2
	Left1 -> C1 -> C2 -> C3 -> Right3
	Left0 -> Bottom3 -> Bottom2 -> Bottom1 -> Bottom0

	edge[style=invis]
	rank=same {Top0 -> Left3 -> Left2 -> Left1 -> Left0}
	rank=same {Top1 -> A1 -> B1 -> C1 -> Bottom3}
	rank=same {Top2 -> A2 -> B2 -> C2 -> Bottom2}
	rank=same {Top3 -> A3 -> B3 -> C3 -> Bottom1}
	rank=same {Right0 -> Right1 -> Right2 -> Right3 -> Bottom0}
}

如上图所示，将矩阵顺时针旋转90度，相当于将Top行移动到Right列，Right列移动到Bottom行，Bottom行移动到Left列，Left列移动到Top行。我们只要按照旋转方向逐个交换以上四行/列中的元素（也就是 Top[0] → Right[0] → Bottom[0] → Left[0] → Top[0]， Top[1] → Right[1] → Bottom[1] → Left[1] → Top[1]等等），即可在\(O(1)\)的空间复杂度之内将矩阵外层旋转90度，矩阵内层也是同理，所以我们从外层到内层逐层进行交换操作即可。

代码

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        size = len(matrix)
        top_left = 0
        bottom_right = size - 1
        square_size = size

        while top_left < bottom_right and square_size > 1:
            for i in range(top_left, bottom_right):
                reverse_i = bottom_right - (i - top_left)
                temp = matrix[top_left][i]
                matrix[top_left][i] = matrix[reverse_i][top_left]
                matrix[reverse_i][top_left] = matrix[bottom_right][reverse_i]
                matrix[bottom_right][reverse_i] = matrix[i][bottom_right]
                matrix[i][bottom_right] = temp

            top_left += 1
            bottom_right -= 1
            square_size -= 2