Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place?

Hint

• Try thinking about it layer by layer. Can you rotate a specific layer?
• Rotating a specific layer would just mean swapping the values in four arrays. If you were asked to swap the values in two arrays, could you do this? Can you then extend it to four arrays?

Solution

以顺时针旋转90为例，旋转图片本质上就是对二维数组的处理。
首先看一种直接的方法，对于当前位置，计算旋转后的新位置，然后再计算下一个新位置，直到第四个位置又旋转到了第一个位置，每次循环四个数字。
| 1 2 3 | | 7 2 1 | | 7 4 1 |
| 4 5 6 | | 4 5 6 | | 8 5 2 |
| 7 8 9 | | 9 8 3 | | 9 6 3 |

public void rotateMatrix(int[][] matrix) {
    if (matrix == null || matrix.length == 0) return;
    int n = matrix.length;
    for (int i = 0; i < n / 2; i++) {
        for (int j = i; j < n - 1 - i; j++) {
            int tmp = 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] = tmp;
        }
    }
}

再看一种解法，先以副对角线为轴进行翻转，再以x轴中线上下翻转。
| 1 2 3 | | 9 6 3 | | 7 4 1 |
| 4 5 6 | | 8 5 2 | | 8 5 2 |
| 7 8 9 | | 7 4 1 | | 9 6 3 |

public void rotateMatrix(int[][] matrix) {
    if (matrix == null || matrix.length == 0) return;
    int n = matrix.length;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i; j++) {
            int tmp = matrix[i][j];
            matrix[i][j] = matrix[n - 1 - j][n - 1 - i];
            matrix[n - 1 - j][n - 1 - i] = tmp;
        }
    }
    for (int i = 0; i < n / 2; i++) {
        for (int j = 0; j < n; j++) {
            int tmp = matrix[i][j];
            matrix[i][j] = matrix[n - 1 - i][j];
            matrix[n - 1 - i][j] = tmp;
        }
    }
}