程序员面试金典 - 面试题 01.07. 旋转矩阵

题目难度: 中等

原题链接

今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~

题目描述

给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。

不占用额外内存空间能否做到？

示例 1:

给定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],

原地旋转输入矩阵，使其变为:
[
[7,4,1],
[8,5,2],
[9,6,3]
]

示例 2:

给定 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]
]

题目思考

1. 如何做到原地修改, 从而不占用额外空间?

解决方案

思路

• 分析题目, 通过观察前几个数字的旋转, 不难发现:
  1. 所有数字都会以 4 个一组进行旋转, 除了奇数 n 的最中间数字
     • 例如对于 4*4 矩阵, (0,0)=>(0,3)=>(3,3)=>(3,0)这是一组; (0,1)=>(1,3)=>(3,2)=>(2,0)这是另一组
     • 第 0 行共有 3 组 (n-1), 即起始数字为(0,0), (0,1), (0,2); 第 1 行共有 1 组 (n-3), 即起始数字为(1,1)
  2. 对于任意数字(r,c), 它会旋转到(c,n-r-1)的位置
     • 例如对于 4*4 矩阵, (0,0)会转到(0,3); (0,1)会转到(1,3); (1,0)会转到(0,2); (3,0)会转到(0,0)
• 根据规律 1, 我们可以得到所有起始数字的行列取值范围:
  • 行号不超过 n/2 (因为组数是 n-1-2r, 它要大于 0);
  • 列号介于[r,n-r-1)之间
• 根据规律 2, 我们可以得到每组数字的转换关系:
  • (r,c) => (c,n-r-1) => (n-r-1,n-c-1) => (n-c-1,r) => (r,c)
• 利用上述结论, 只需要两重循环, 定义起始数字和转换方程即可做到原地转换

复杂度

• 时间复杂度 O(N^2): 需要遍历矩阵一遍
• 空间复杂度 O(1): 只使用了几个变量

代码

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        # 画图理解, 4方向旋转, 注意下标的变换
        # 注意起始数字r和c的边界, 只需要旋转([0,n-1), [1,n-2), [2, n-3)...)即可
        n = len(matrix)
        for r in range(n // 2):
            for c in range(r, n - r - 1):
                tmp = matrix[r][c]
                # (n-c-1,r) => (r,c)
                matrix[r][c] = matrix[n - c - 1][r]
                # (n-r-1,n-c-1) => (n-c-1,r)
                matrix[n - c - 1][r] = matrix[n - r - 1][n - c - 1]
                # (c,n-r-1) => (n-r-1,n-c-1)
                matrix[n - r - 1][n - c - 1] = matrix[c][n - r - 1]
                # (r,c) => (c,n-r-1)
                matrix[c][n - r - 1] = tmp

大家可以在下面这些地方找到我~😊

我的知乎专栏

我的头条号

我的 CSDN

我的 Leetcode

我的牛客网博客

我的公众号: 算法精选, 欢迎大家扫码关注~😊