面试题 01.07. 旋转矩阵

面试题 01.07. 旋转矩阵 #

  • 标签:数组、数学、矩阵
  • 难度:中等

题目大意 #

给定一个 n * n 大小的二维矩阵用来表示图像,其中每个像素的大小为 4 字节。

要求:设计一种算法,将图像旋转 90 度。并且要不占用额外内存空间。

解题思路 #

题目要求不占用额外内存空间,就是要在原二维矩阵上直接进行旋转操作。我们可以用翻转操作代替旋转操作。具体可以分为两步:

  1. 上下翻转。

  2. 主对角线翻转。

举个例子:

1
2
3
4
 1  2  3  4
 5  6  7  8
 9 10 11 12              
13 14 15 16              

上下翻转后变为:

1
2
3
4
13 14 15 16
 9 10 11 12
 5  6  7  8
 1  2  3  4 

在经过主对角线翻转后变为:

1
2
3
4
13  9  5  1
14 10  6  2
15 11  7  3
16 12  8  4

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        size = len(matrix)
        for i in range(size // 2):
            for j in range(size):
                matrix[i][j], matrix[size - i - 1][j] = matrix[size - i - 1][j], matrix[i][j]
        for i in range(size):
            for j in range(i):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
本站总访问量  次  |  您是本站第  位访问者