题目难度: 中等

原题链接[1]

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

题目描述

给你一幅由 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.         """         # 画图理解, 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

参考资料

[1]

原题链接: https://leetcode-cn.com/problems/rotate-matrix-lcci/