Rotate Image

48. Rotate Image

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

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:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[7,4,1],[8,5,2],[9,6,3]]

Example 2:

Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

Constraints:

• n == matrix.length == matrix[i].length

• 1 <= n <= 20

• -1000 <= matrix[i][j] <= 1000

My Solutions:

方法1: 根据观察，可以发现这个规律：先是最外面一圈变化，然后内圈再变化。最多变化的次数是正方形边长的一半。

外圈的数字是这样移动的：

element at (0, 0) --> element at (0, 3) --> element at (3, 3) --> element at (3,0) --> element at (0, 0)

相似的，element at (0, 1) --> element at (1, 3) --> element at (3, 2) --> element at (2,0) --> element at (0, 1)，可以总结出步骤：

• 先在temp存上element at (2, 0)

• element at (2, 0) 变成 element at (3, 2)

• element at (3, 2) 变成 element at (1, 3)

• element at (1, 3) 变成 element at (0, 1)

• element at (0, 1) 变成 temp

    public void rotate(int[][] matrix) {
        int len = matrix.length;
        // the times needed to rotate is the half of the len
        for (int i = 0; i < (len + 1) / 2; i++) {
            for (int j = 0; j < len / 2; j++) {
                // record the number at the bottom-left corner
                int temp = matrix[len - 1  - j][i]; // note that the i and j in matrix[][] rotates
                
                // replace bottom-left into the bottom-right corner
                matrix[len - 1 - j][i] = matrix[len - 1 - i][len - j - 1];
                
                // replace bottem-right into top-left
                matrix[len - 1 - i][len - j - 1] = matrix[j][len - 1 - i];
                
                // replace top-left with top-right corner
                matrix[j][len - 1 - i] = matrix[i][j];
                
                matrix[i][j] = temp;
            }
        }
    }

方法2: The most elegant solution for rotating the matrix is to firstly reverse the matrix around the main diagonal, and then reverse it from left to right. These operations are called transpose and reflect in linear algebra.

transpose: reflect:

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

[4,5,6] --> [2,5,8] -->[8,5,2]

[7,8,9] [3,6,9] [9,6,3]

    public void rotate(int[][] matrix) {
        transpose(matrix);
        reflect(matrix);
    }
    
    public void transpose(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) { // note here is j = i + 1 because at the element at j = i does not need to be moved
                int tmp = matrix[j][i];
                matrix[j][i] = matrix[i][j];
                matrix[i][j] = tmp;
            }
        }
    }
    
    public void reflect(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n / 2; j++) { // n / 2 because we're swapping the left and right
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[i][n - j - 1];
                matrix[i][n - j - 1] = tmp;
            }
        }
    }