Rotate Image

You are given annxn2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Follow up: Could you do this in-place?

算法1

先将矩阵转置，然后把转置后的矩阵每一行翻转

转置变为 每一行翻转变为

class Solution(object):
    def rotate(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: void Do not return anything, modify matrix in-place instead.
        """
        length = len(matrix)
        for i in range(length):
            for j in range(i+1,length):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

        for i in range(length):
            matrix[i].reverse()

算法2

可以见矩阵看成多个环组成，如下4*4的矩阵包括两个环，第一个环为1,2,3,4,8,12,16,15,14,13,9,5,1，第二个环为6,7,11,10。

旋转一个矩阵，相当于把每一个环都旋转。如何旋转一个环呢？以最外层的环举例： 本文地址

旋转前：，旋转后：

我们把环分成3组：{1,4,16,13}，{2,8,15,9}，{3,12,14,5}，每一组中：旋转后相当于把原来的数字移动到同组中下一个数字的位置

对于一个n*n的矩阵可以分成n/2（向上取整）个环来旋转；对于边长为len的环，可以分成len-1组来旋转。