LeetCode解题报告(48)--矩阵的旋转

原题如下: You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Follow up: Could you do this in-place? 题目要求将图片顺时针翻转90度。通过用一个额外的图片矩阵来存储这个图片能够轻松完成,但是题目最后说了Could you do this in-place?,意思是能否通过O(1)的空间复杂度完成这项任务。

这就需要一点技巧了,下面以一个例子说明如何不借助额外的图片矩阵完成顺时针90度旋转。

1
2
3
1 2 3     7 8 9     7 4 1
4 5 6 --> 4 5 6 --> 8 5 2
7 8 9 1 2 3 9 6 3
首先将图片的行上下对称交换,假如有奇数行,中间的行不用动;假如有偶数行,则全部都要对称交换。然后将矩阵转置即可。

具体实现代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
def rotate(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: void Do not return anything, modify matrix in-place instead.
"""
n = len(matrix)
for i in xrange(n/2):
matrix[i], matrix[n-1-i] = matrix[n-1-i], matrix[i]

for i in xrange(n):
for j in xrange(i+1,n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

参考上面的方法,同理可以推出逆时针旋转90度和旋转180度的实现方法。

逆时针旋转90度

将矩阵的列左右对称交换,然后转置。例子如下所示

1
2
3
1 2 3     3 2 1     3 6 9
4 5 6 --> 6 5 4 --> 2 5 8
7 8 9 9 8 7 1 4 7

旋转180度 上下对称交换,然后左右对称交换。例子如下所示:

1
2
3
1 2 3     7 8 9     9 8 7
4 5 6 --> 4 5 6 --> 6 5 4
7 8 9 1 2 3 3 2 1