Problem: 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?

Solution: Rotate Image, Python:

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
26
27
28
#!/usr/bin/env python
# -*- encoding: utf-8 -*-
# @Date : 2015-01-29 22:50:57
# @Author : NSSimacer
# @Version : 1.0
class Solution:
# @param matrix, a list of lists of integers
# @return a list of lists of integers
def rotate(self, matrix):
n = len(matrix)
for i in xrange(n):
for j in xrange(i, n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
for i in xrange(n):
matrix[i] = matrix[i][::-1]
return matrix

思路一: 从外到内一圈一圈地转(慢);
思路二: 沿主对角线反转一次,再把矩阵行元素反转;

根据思路二实现,Python可以简洁实现元素交换和列表反转,时间复杂度O(N^2),空间复杂度O(1)。