LeetCode in Python 48. Rotate Image/Matrix (旋转图像/矩阵)-Toy模板网

这篇具有很好参考价值的文章主要介绍了LeetCode in Python 48. Rotate Image/Matrix (旋转图像/矩阵)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

示例：

LeetCode in Python 48. Rotate Image/Matrix (旋转图像/矩阵),Leecode题解,leetcode,python,算法,数据结构

图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各为一小圈。

LeetCode in Python 48. Rotate Image/Matrix (旋转图像/矩阵),Leecode题解,leetcode,python,算法,数据结构

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() 空间来保存原始矩阵。

另外附上另一种实现方式：文章来源地址https://www.toymoban.com/news/detail-860355.html

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

到了这里，关于LeetCode in Python 48. Rotate Image/Matrix (旋转图像/矩阵)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！