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