Problem

You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).

Example

Given a matrix

[
    [1,2],
    [3,4]
]

rotate it by 90 degrees (clockwise), return

[
    [3,1],
    [4,2]
]

Challenge

Do it in-place.

Note

两种方法，转置镜像法和公式法。
首先看转置-镜像法：
原矩阵为：

1  2  3             
4  5  6
7  8  9
(original)

转置后：(matrix[i][j] --> matrix[j][i])

1  4  7
2  5  8
3  6  9
(transposed)

水平镜像翻转后：(matrix[i][j] --> matrix[i][matrix.length-1-j])

7  4  1
8  5  2
9  6  3
(flipped horizontally)   

所以，基本的思路是两次遍历，第一次转置，第二次水平镜像翻转（变换列坐标）。
需要注意的是，转置操作是对于左上角-右下角对角线所分割的右侧三角形矩阵进行的，即只对二分之一个矩阵进行转置；水平镜像翻转时，对列不做完全循环，而是从0到n/2。否则翻转后的前二分之一列坐标会再次被翻转回去。

公式法是应用了一个翻转90°的公式：newRow = width - oldCol, newCol = oldRow,
如此翻转四次即可。
需要注意遍历矩阵时的循环边界条件，有两种写法:

1.

for (int i = 0; i < (n+1)/2; i++) {
    for (int j = 0; j < n/2; j++) {

2.

for (int i = 0; i < n; i++) {
    for (int j = i; j < n-1-i; j++) {

第一种写法是翻转左上方四分之一个矩阵；第二种写法是翻转以对角线分割的上方的三角形矩阵。二者均可，并无分别。

Solution

转置-镜像法

public class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n/2; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[i][n-1-j];
                matrix[i][n-1-j] = temp;
            }
        }
    }
}

公式法I.

public class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < (n+1)/2; i++) {
            for (int j = 0; j < n/2; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n-1-j][i];
                matrix[n-1-j][i] = matrix[n-1-i][n-1-j];
                matrix[n-1-i][n-1-j] = matrix[j][n-1-i];
                matrix[j][n-1-i] = temp;
            }
        }
    }
}

公式法II.

public class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n-1-i; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n-1-j][i];
                matrix[n-1-j][i] = matrix[n-1-i][n-1-j];
                matrix[n-1-i][n-1-j] = matrix[j][n-1-i];
                matrix[j][n-1-i] = temp;
            }
        }
    }
}