【LeetCode with Python】 Rotate Image

2024-01-10 07:57:28

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Follow up:
Could you do this in-place?

题意分析：
顺时针90度转动一个二维矩阵，要求in-place的算法，也就不是不能另外开一个新的矩阵然后把原矩阵上的元素一个个对应复制过来，而要在原矩阵上进行操作。

算法分析：
目前能想到的有两种方法。
第一种比较直观，首先将原矩阵按照水平轴上下翻转，然后按照左上到右下的对角线再反转，则等价于90度顺时针转动。这个方法的缺点是要反转两次，优点是直观，不容易出错。
第二种方法每个元素只需要调整一次，但是转化公式会比较复杂。对于矩阵matrix[n][n]中的某一点matrix[x][y]（0<=x, y<n），90度顺时针转动后到了matrix[y][n-x-1]，而matrix[y][n-x-1]到了matrix[n-x-1][n-y-1]，matrix[n-x-1][n-y-1]到了matrix[n-y-1][x]，matrix[n-y-1][x]又到了matrix[x][y]，可见这四个点正好实现了一次旋转互换。
本文采用第二种方法，空间复杂度O(1)，时间复杂度O(n*n)。

防坑警报：
n=1时直接返回原矩阵即可。

class Solution:
    # @param matrix, a list of lists of integers
    # @return a list of lists of integers
    def rotate(self, matrix):
        n = len(matrix)
        if 1 == n:
            return matrix
        round = int(n / 2)
        for x in range(0, round):
            for y in range(x, n - x - 1):
                tmp = matrix[n - y - 1][x]
                matrix[n - y - 1][x] = matrix[n - x - 1][n - y - 1]
                matrix[n - x - 1][n - y - 1] = matrix[y][n - x - 1]
                matrix[y][n - x - 1] = matrix[x][y]
                matrix[x][y] = tmp
        return matrix

【LeetCode with Python】 Rotate Image

码农公寓

相关文章