题目链接
LeetCode 面试题 01.07. 旋转矩阵[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]]
题解
旋转
可以发现,每个格子旋转四次之后都会回到原位。所以对于每个格子,我们只需要交换和它相关的一共四个格子的位置就行了。
对于格子 (i, j)
,我们可以推算出它旋转后的三个新位置是 (j, n-1-i), (n-1-i, n-1-j), (n-1-j, i)
。所以只需要一个临时变量保存其中一个位置的值,然后按顺序交换位置就行了。
当然为了避免重复旋转,我们只能枚举四分之一的格子,如果 n
是偶数,如下图所示,我们可以这划分:
如果 n
是奇数,可以如下图这么划分:
当然你也可以不规则的划分,如下图这样,只是代码写起来有点费劲:
翻转
这题还可以不通过模拟旋转来实现旋转。
上面说过了,格子 (i, j)
旋转后的新位置是 (j, n-1-i)
。
那么我们可以先沿着主对角线翻转矩阵,这样格子 (i, j)
位置就换到了 (j, i)
。
然后再左右翻转一下矩阵,格子 (j, i)
就换到了 (j, n-1-i)
,正好等价于旋转后的位置!
因为翻转每次只需要交换两个格子的位置,所以不需要任何额外变量。
再提一个交换两个元素的小 trick ,如代码里注释的那样,可以采用异或操作来规避额外变量。
代码
旋转(c++)
classSolution { public: voidrotate(vector<vector<int>>&matrix) { intn=matrix.size(); for (inti=0; i<n/2; ++i) { for (intj=0; j< (n+1)/2; ++j) { inttmp=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] =matrix[i][j]; matrix[i][j] =tmp; } } } };
翻转(c++)
classSolution { public: voidrotate(vector<vector<int>>&matrix) { intn=matrix.size(); for (inti=0; i<n; ++i) { for (intj=i+1; j<n; ++j) { matrix[i][j] ^=matrix[j][i]; matrix[j][i] ^=matrix[i][j]; matrix[i][j] ^=matrix[j][i]; // swap(matrix[i][j], matrix[j][i]); } } for (inti=0; i<n; ++i) { for (intj=0; j<n/2; ++j) { matrix[i][j] ^=matrix[i][n-1-j]; matrix[i][n-1-j] ^=matrix[i][j]; matrix[i][j] ^=matrix[i][n-1-j]; // swap(matrix[i][j], matrix[i][n-1-j]); } } } };
旋转(python)
classSolution: defrotate(self, matrix: List[List[int]]) ->None: n=len(matrix) foriinrange(n//2): forjinrange((n+1)//2): tmp=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] =matrix[i][j] matrix[i][j] =tmp
翻转(python)
classSolution: defrotate(self, matrix: List[List[int]]) ->None: n=len(matrix) foriinrange(n): forjinrange(i+1, n): matrix[i][j], matrix[j][i] =matrix[j][i], matrix[i] [j] foriinrange(n): forjinrange(n//2): matrix[i][j], matrix[i][n-1-j] =matrix[i] [n-1-j], matrix[i][j]
关注【算法码上来】,每日算法干货马上就来!
参考资料
[1]
LeetCode 面试题 01.07. 旋转矩阵: https://leetcode-cn.com/problems/rotate-matrix-lcci/
作者简介:godweiyang,知乎同名,华东师范大学计算机系硕士在读,方向自然语言处理与深度学习。喜欢与人分享技术与知识,期待与你的进一步交流~