本文共 2295 字，大约阅读时间需要 7 分钟。

题目地址：

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Note:

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Example 1:

Given input matrix = [  [1,2,3],  [4,5,6],  [7,8,9]],rotate the input matrix in-place such that it becomes:[  [7,4,1],  [8,5,2],  [9,6,3]]

Example 2:

Given input matrix =[  [ 5, 1, 9,11],  [ 2, 4, 8,10],  [13, 3, 6, 7],  [15,14,12,16]], rotate the input matrix in-place such that it becomes:[  [15,13, 2, 5],  [14, 3, 4, 1],  [12, 6, 8, 9],  [16, 7,10,11]]

这个题目本身不难理解，如果能够再开辟一个n*n的空间出来，其实也不难，难就难在人家要求原地（in-place）旋转。

原地旋转可以这么搞：

1. 行之间对换：第一行与最后一行对换，第二行与倒数第二行对换，……
2. 对角元素对换：matrix[i][j]<->matrix[j][i]

直接上例子

原矩阵

$$\begin{bmatrix}1&2&3\\4&5&6\\7&8&9\end{bmatrix}$$

交换行之后：

$$\begin{bmatrix}7&8&9\\4&5&6\\1&2&3\end{bmatrix}$$

对角元素调换：

$$\begin{bmatrix}7&4&1\\8&5&2\\9&6&3\end{bmatrix}$$

好了，大功告成，直接上源码：

public class RotateImage {    public static void rotate(int[][] matrix) {        if (matrix == null)            return;        if (matrix.length == 0)            return;        int begin = 0;        int end = matrix.length - 1;        while (begin < end) {            for (int i = 0; i < matrix.length; i++) {                int tmp = matrix[begin][i];                matrix[begin][i] = matrix[end][i];                matrix[end][i] = tmp;            }            begin++;            end--;        }        for (int i = 0; i < matrix.length; i++) {            for (int j = 0; j < i; j++) {                int tmp = matrix[i][j];                matrix[i][j] = matrix[j][i];                matrix[j][i] = tmp;            }        }    }    public static void printMatrix(int[][] matrix) {        if (matrix == null)            return;        if (matrix.length == 0)            return;        for (int i = 0; i < matrix.length; i++) {            for (int j = 0; j < matrix[i].length; j++) {                System.out.print(matrix[i][j] + " ");            }            System.out.println();        }    }    public static void main(String[] args) {        int[][] matrix = new int[][]{
  {
  1, 2, 3}, {
  4, 5, 6}, {
  7, 8, 9}};        System.out.println("-----before rotate------");        printMatrix(matrix);        rotate(matrix);        System.out.println("-----after rotate-------");        printMatrix(matrix);    }}

时间复杂度$O(n^2)$。

转载地址：http://yihii.baihongyu.com/