题目难度: 中等
原题链接
今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~
题目描述
给你一幅由 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]
]
题目思考
如何做到原地修改, 从而不占用额外空间?
解决方案
思路
分析题目, 通过观察前几个数字的旋转, 不难发现:
所有数字都会以 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) 对于任意数字(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.
"""
n
= len(matrix
)
for r
in range(n
// 2):
for c
in range(r
, n
- r
- 1):
tmp
= matrix
[r
][c
]
matrix
[r
][c
] = matrix
[n
- c
- 1][r
]
matrix
[n
- c
- 1][r
] = matrix
[n
- r
- 1][n
- c
- 1]
matrix
[n
- r
- 1][n
- c
- 1] = matrix
[c
][n
- r
- 1]
matrix
[c
][n
- r
- 1] = tmp
大家可以在下面这些地方找到我~😊
我的知乎专栏
我的头条号
我的
我的 Leetcode
我的牛客网博客
我的公众号: 算法精选, 欢迎大家扫码关注~😊
