本题来自Leetcode48:旋转图像
我们熟悉图像的旋转问题,而这个问题要求在原地旋转,即不能用额外的矩阵(空间复杂度o(1))。输入输出都是二维列表。
所以,收起将列表转化为numpy的想法。
如果您之前没接触这个问题,也容易想到去考察两个二维列表之间元素的对应关系。
假设a=
[[1,2,3],
[4,5,6],
[7,8,9]]
旋转之后就是
[[7,4,1],
[8,5,2],
[9,6,3]]
二者的相对位置关系是什么?最明显的是四个对角区域1,3,7,9的关系:四者是互相交换得到的:
(0,0)位置的元素1到了(0,2)位置,
(0,2)位置的元素2到了(2,2)位置,
(2,2)位置的元素9到了(2,0)位置,
(2,0)位置的元素7到了(0,0)位置,
然后你会发现,对于最外层的数,都可以用四数交换的方式来完成交换。例如4,2,6,8之间也是类似的互相交换。在交换最外一层的数时,对二维数组里层的数是没有影响的。
换句话说,这个问题可以像剥洋葱一样,按二维数组从外到里的次序分别完成四数交换。
考虑一个更大的二维列表:
[[1, 2, 3, 4, 5, 6],
[7, 8, 9, 10, 11, 12],
[13, 14, 15, 16, 17, 18],
[19, 20, 21, 22, 23, 24],
[25, 26, 27, 28, 29, 30],
[31, 32, 33, 34, 35, 36]]
注意交换(0,0)的时候已经涉及到(0,5)和(5,5),(5,0)了。所以对于最外层,需要进行四数交换的只需要考虑 (0,0),(0,1),(0,2),(0,3),(0,4)五组位置。(毕竟最外层一共只有20个数字,只能进行5组四数交换)
然后可能会发现,能否让下一次输入的时候,每次向内一层,比如:
[[8,9,10,11],
[14,15,16,17],
[20,21,22,23],
[26,27,28,29]]
将旋转之后的结果作为输出,更新当前数组的内层?这样内层貌似都可以解决了。
但问题在于题目的输入二维数组,是没办法像numpy直接切片的。。
所以这条路应该走不通。
还是要老老实实像前面一样继续探索旋转前后的位置关系。不难发现,对于上面的6x6二维数组存在下面的关系:
temp = matrix[j][i]
matrix[j][i] = matrix[5-i][j]
matrix[5-i][j] = matrix[5-j][n-i]
matrix[5-j][5-i] = matrix[i][5-j]
matrix[i][5-j] = temp
所以最后的问题就是,对于每一层,有哪些是要进行四数交换的位置?
这个问题比较明显:
最外层是(0,0),…,(0,4)
次外层是(1,1),…,(1,3)
里层是(2,2)
规律还是很明显的。所以写两个循环,外循环控制层数(x坐标),内循环控制y坐标,就可以了。
完整代码
def rotate(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: None Do not return anything, modify matrix in-place instead.
"""
n = len(matrix)-1
#比如说matrix长度是4,n=3,那么需要更改的外层只有[0,0],[0,1],[0,2]
for j in range(int(len(matrix)/2)):
# j = 1
for i in range(j,n-j):
# print(j,i)
temp = matrix[j][i]
matrix[j][i] = matrix[n-i][j]
matrix[n-i][j] = matrix[n-j][n-i]
matrix[n-j][n-i] = matrix[i][n-j]
matrix[i][n-j] = temp
# print(matrix)
return matrix