全栈开发知识库

36.旋转图像

题目

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

示例1:

image

  • 输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
  • 输出：[[7,4,1],[8,5,2],[9,6,3]]

示例2:

image

  • 输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
  • 输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

提示:

  • n == matrix.length == matrix[i].length
  • 1 <= n <= 20
  • -1000 <= matrix[i][j] <= 1000

思路

方法一： 辅助矩阵

如下图所示，矩阵顺时针旋转 90º 后，可找到以下规律:

  • 「第 i 行」元素旋转到「第 n−1−i 列」元素；
  • 「第 j 列」元素旋转到「第 j 行」元素；

因此，对于矩阵任意第 i 行、第 j 列元素 matrix[i][j] ，矩阵旋转 90º 后「元素位置旋转公式」为:

  • 原索引位置 →旋转后索引位置

  • matrix[i][j] → matrix[j][n−1−i]

根据以上「元素旋转公式」，考虑遍历矩阵，将各元素依次写入到旋转后的索引位置。但仍存在问题：在写入一个元素 matrix[i][j]→matrix[j][n−1−i] 后，原矩阵元素 matrix[j][n−1−i] 就会被覆盖（即丢失），而此丢失的元素就无法被写入到旋转后的索引位置了。

为解决此问题，考虑借助一个「辅助矩阵」暂存原矩阵，通过遍历辅助矩阵所有元素，将各元素填入「原矩阵」旋转后的新索引位置即可。

image

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        n = len(matrix)
        # 深拷贝 matrix -> tmp
        tmp = copy.deepcopy(matrix)
        # 根据元素旋转公式，遍历修改原矩阵 matrix 的各元素
        for i in range(n):
            for j in range(n):
                matrix[j][n - 1 - i] = tmp[i][j]

复杂度分析:

  • 遍历矩阵所有元素的时间复杂度为O(N²)
  • 由于借助了一个辅助矩阵，空间复杂度为O(N²)。
方法二：原地修改

考虑不借助辅助矩阵，通过在原矩阵中直接「原地修改」，实现空间复杂度 O(1) 的解法。

以位于矩阵四个角点的元素为例，设矩阵左上角元素A、右上角元素B、右下角元素C、左下角元素D。

矩阵旋转90º后，相当于依次先后执行D→A,C→D,B→C,A→B修改元素，即如下「首尾相接」的元素旋转操作: 

A←D←C←B←A

image

如上图所示:

  • 由于第1步D→A已经将A覆盖（导致A丢失），此丢失导致最后第4步A→B无法赋值。为解决此问题，考虑借助一个「辅助变量 tmp 」预先存储 A ，此时的旋转操作变为：
暂存 tmp=A
A←D←C←B←tmp

image

如上图所示，一轮可以完成矩阵 4 个元素的旋转。因而，只要分别以矩阵左上角 1/4 的各元素为起始点执行以上旋转操作，即可完整实现矩阵旋转。

  • 当矩阵大小 n 为偶数时，取前½ * n行、前 ½ * n 列的元素为起始点；

  • 当矩阵大小 n 为奇数时，取前 ½ * n 行、前 ½ * (n + 1)列的元素为起始点。

令 matrix[i][j]=A ，根据文章开头的元素旋转公式，可推导得适用于任意起始点的元素旋转操作：

暂存tmp=matrix[i][j]
matrix[i][j]←matrix[n−1−j][i]←matrix[n−1−i][n−1−j]←matrix[j][n−1−i]←tmp

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

class Solution {
    public void rotate(int[][] matrix) {
        // 设矩阵行列数为 n
        int n = matrix.length;
        // 起始点范围为 0 <= i < n / 2 , 0 <= j < (n + 1) / 2
        // 其中 '/' 为整数除法
        for (int i = 0; i < n / 2; i++) {
            for (int j = 0; j < (n + 1) / 2; j++) {
                // 暂存 A 至 tmp
                int tmp = matrix[i][j];
                // 元素旋转操作 A <- D <- C <- B <- tmp
                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] = tmp;
            }
        }
    }
}

复杂度分析:

  • 时间复杂度 O(N²): 其中 N 为输入矩阵的行（列）数。需要将矩阵中每个元素旋转到新的位置，即对矩阵所有元素操作一次，使用O(N²)时间。
  • 空间复杂度 O(1): 临时变量 tmp 使用常数大小的额外空间。值得注意，当循环中进入下轮迭代，上轮迭代初始化的 tmp 占用的内存就会被自动释放，因此无累计使用空间。
方法三: 先转置再左右翻转

或者记一个更简单的规律:

  • 顺时针 90° = 转置 + 每行左右翻转
  • 逆时针 90° = 转置 + 每列上下翻转（即翻转行的顺序）

很明显可以发现，对二位矩阵顺时针旋转90度，等价于先对二位矩阵进行转置操作，再对转置后的数组进行左右翻转。 原矩阵： 

1   2   3
4   5   6
7   8   9

转置后：

1   4   7
2   5   8   
3   6   9

左右翻转：

7   4   1   
8   5   2   
9   6   3

可以发现，顺时针旋转90度后的矩阵，于先转置再左右翻转的矩阵相同

1、矩阵转置:

矩阵的转置是将矩阵的行和列互换，即将元素 matrix[i][j] 和 matrix[j][i] 交换。

性质:

  • 转置操作不会改变主对角线上的元素（即 i=j 时的元素）。

  • 转置完成后，矩阵变为关于主对角线对称。

本质：将矩阵对角线两边的元素互换

2、逐行翻转:

  • 对转置后的矩阵，每一行进行翻转，即从左到右交换元素，得到最终旋转后的结果。

性质： 转置只是调整了行列的关系，但要实现顺时针旋转 90 度，还需要将转置后的行元素顺序反转。

全部代码: 

class Solution:
    def transpose(self, matrix:List[List[int]]) -> None:
        length = len(matrix)
        for i in range(0, length):
            for j in range(0, i):
                temp = matrix[i][j]
                matrix[i][j] = matrix[j][i]
                matrix[j][i] = temp

    def overturn(self, matrix:List[List[int]]) -> None:
        length = len(matrix)
        for i in range(0, length//2):
            for j in range(0, length):
                temp = matrix[j][i]
                matrix[j][i] = matrix[j][length - 1 - i]
                matrix[j][length - 1 - i] = temp

    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        self.transpose(matrix)
        self.overturn(matrix)

class Solution {
    fun rotate(matrix: Array<IntArray>) {
        val n = matrix.size

        // ① 转置：沿主对角线交换 (i,j) 和 (j,i)
        // 注意 j 从 i 开始，只处理上三角，避免交换两次又换回来
        for (i in 0 until n) {
            for (j in i until n) {
                val temp = matrix[i][j]
                matrix[i][j] = matrix[j][i]
                matrix[j][i] = temp
            }
        }

        // ② 每一行左右翻转
        for (i in 0 until n) {
            var left = 0
            var right = n - 1
            while (left < right) {
                val temp = matrix[i][left]
                matrix[i][left] = matrix[i][right]
                matrix[i][right] = temp
                left++
                right--
            }
        }
    }
}
  • 时间复杂度: O(N²)

  • 空间复杂度: O(1)

  • 下一题

  • 邮箱 ：charon.chui@gmail.com
  • Good Luck!