# 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**

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

[![image](http://images.cnitblog.com/blog/517264/201406/042138459422788.png)](http://images.cnitblog.com/blog/517264/201406/042138455207616.png) 转置变为 [![image](http://images.cnitblog.com/blog/517264/201406/042138467707901.png)](http://images.cnitblog.com/blog/517264/201406/042138465677430.png) 每一行翻转变为[![image](http://images.cnitblog.com/blog/517264/201406/042138463171974.png)](http://images.cnitblog.com/blog/517264/201406/042138460997273.png)

```
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。

[![image](http://images.cnitblog.com/blog/517264/201406/042138472864045.png)](http://images.cnitblog.com/blog/517264/201406/042138469892602.png)

旋转一个矩阵，相当于把每一个环都旋转。如何旋转一个环呢？以最外层的环举例： [本文地址](http://www.cnblogs.com/TenosDoIt/p/3768734.html)

旋转前：[![image](http://images.cnitblog.com/blog/517264/201406/042138478177715.png)](http://images.cnitblog.com/blog/517264/201406/042138475206272.png)，旋转后：[![image](http://images.cnitblog.com/blog/517264/201406/042138482081130.png)](http://images.cnitblog.com/blog/517264/201406/042138480529942.png)

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

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

```
```
