###48. Rotate Image


题目:
<https://leetcode.com/problems/rotate-image/>


难度:

Medium



思路一：

```
rotate之前：             之后：
 1	2	3	4			13	9	5	1
 5	6	7	8			14	10	6	2
 9	10	11	12			15	11	7	3
 13	14	15	16			16	12	8	4

```
看网上的hint，是先沿着对角线变换一次，再验证水平中线变换一次


```
16	12	8	4			13	9	5	1
15	11	7	3			14	10	6	2
14	10	6	2			15	11	7	3
13	9	5	1			16	12	8	4
```

对角线变换的规律是
(i,j), (n-1-j,n-1-i) 

上下变换规律
(i,j),(n-1-i,j)


```
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 range(n):
        	for j in range(n):
        		if j < n-1-i:
        			matrix[i][j],matrix[n-1-j][n-1-i] = matrix[n-1-j][n-1-i],matrix[i][j]

        for i in range(n/2):
        	for j in range(n):
        		matrix[i][j],matrix[n-1-i][j] = matrix[n-1-i][j],matrix[i][j]
        

```


思路二：

参考这里

<http://www.lifeincode.net/programming/leetcode-rotate-image-java/>

找规律，一次完成四个数的该有的变换

```

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 

```

观察一下，第一个数开始的变换是 (0,0)->(0,4)->(4,4)->(4,0)
第二个数的变换是 (0,1)->(1,4)->(4,3)->(3,0)

变换是 (x,y) -> (y, n-1-x) -> (n-1-x,n-1-y)->(n-1-y,x)

然后处理第一行是从(0,0)->(0,n-2)，第二列是(1,1)->(1,n-3).

第i行(i, i)(i, n – 2 – i).终止条件也有了。

虽然都是O(N^2)，但是这个比上面的稍快

```
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)
        
        # row, col
        for i in range(n):
            for j in range(i,n-1-i):
                matrix[i][j],matrix[j][n-1-i],matrix[n-1-i][n-1-j],matrix[n-1-j][i] = \
                matrix[n-1-j][i],matrix[i][j],matrix[j][n-1-i],matrix[n-1-i][n-1-j]
```


这里的问题是矩阵都是方形，如果不是方形，貌似难很多。