[数据结构与算法]程序员面试经典系列(七)：旋转矩阵

题目描述：

给你一幅由 N × N矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。

不占用额外内存空间能否做到？

示例：

输入：给定 matrix = 
[
	[1,2,3],
	[4,5,6],
	[7,8,9]
],

输出：原地旋转输入矩阵，使其变为
[
	[7,4,1],
	[8,5,2],
	[9,6,3]
]

输入：给定 matrix =
[
  [ 5, 1, 9,11],
  [ 2, 4, 8,10],
  [13, 3, 6, 7],
  [15,14,12,16]
], 

输出：原地旋转输入矩阵，使其变为
[
  [15,13, 2, 5],
  [14, 3, 4, 1],
  [12, 6, 8, 9],
  [16, 7,10,11]
]

更多详细描述，可见官网

解题思路

要将矩阵旋转90°，最简单的做法就是一层一层进行旋转。对每一层执行环状旋转：将上边的移到右边，右边移到下边，下边移到左边，左边移到上边。

根据索引一个一个进行交换：

// 伪代码
for i = 0 to n
	temp = top[i];
	top[i] = left[i];
	left[i] = bottom[i];
	bottom[i] = right[i];
	right[i] = temp;

Java代码：

public class Main{
	private static int[][]  rotate(int[][] matrix){
	       if (matrix.length == 0 || matrix.length != matrix[0].length){
	           return null;
	       }
	       int n = matrix.length;
	       for (int layer = 0; layer < n/2; layer++) {
	           int first = layer;
	           int last = n - 1 - layer;
	           for (int i = first; i < last; i++) {
	               int offset = i - first;
	               int top = matrix[first][i];
	               matrix[first][i] = matrix[last-offset][first];
	               matrix[last-offset][first] = matrix[last][last - offset];
	               matrix[last][last - offset] = matrix[i][last];
	               matrix[i][last] = top;
	           }
	       }
	       return matrix;
	}
	
	public static void main(String[] args) {
	       int[][] array = {
	               {1,2,3},
	               {4,5,6},
	               {7,8,9}
	       };
	       int[][] rotate = rotate(array);
	       for (int i = 0; i < rotate.length; i++) {
	           for (int j = 0; j < rotate[0].length; j++) {
	               System.out.print(rotate[i][j]+"  ");
	           }
	           System.out.println();
	       }
	}
}

该题的最优解法也是需要$O(n^2)$的时间复杂度。