Easy to understand Java AC solution - Rotate Image


  • 0
    R
    class Solution {
        public void rotate(int[][] matrix) {
            int n = matrix.length;
            // Math.ceil() is for odd numbers. Odd numbers like 3*3, 1*2 or 2*1 numbers need to rotate
            for(int i=0; i<Math.ceil((double)(n)/2.0); i++){
                for(int j=0; j<n/2; j++){
                    // rotate number in four places
                    int temp = matrix[i][j];
                    matrix[i][j] = matrix[n-1-j][i];
                    matrix[n-j-1][i] = matrix[n-i-1][n-j-1];
                    matrix[n-i-1][n-j-1] = matrix[j][n-i-1];
                    matrix[j][n-i-1] = temp;
                }
            }
        }
    }
    

    This is an interesting thought. If we want to rotate a matrix, one way we can do is to see the outer numbers as a big circle, and inner numbers as smaller circles. What we need is just rotate the circle, to move every number in the circle to their right position. The solution here is to put 4 numbers in the circle to the correct place each time.

    The base case is

    matrix[i][j] = matrix[n-1-j][i];
    

    We put number matrix[n-1-j][i] in position[n-1-j]i to its new position [i]j.
    Then position [n-1-j][i] is empty, we need to find the correct number to fill it in.
    Which number should be in this position?
    We make an equation. Each time the given a new position [i]j, the number to fill it in is put the new row position[newRow], to original column position[oldCol]; and original row position[oldRow] = n - [newCol] - 1.

    So given matrix[n-1-j][i], now n-1-j = [newRow] and i = [newCol] => [oldCol] = [newRow] = n-1-j and [oldRow] = n - 1 - [newCol] = n - 1 - i.
    matrix[newRow][newCol] = [oldRow][oldCol]
    This is why matrix[n-j-1][i] = matrix[n-i-1][n-j-1].

    We do this four times and then get the result;

    As for Math.ceil(), it is designed for odd numbers. even numbers are easy, we rotate n/2n/2 numbers, each of the process we rotate 4 numbers so we rotate nn numbers in total. But for odd numbers, we need to rotate one side n/2+1; like 33 matrix, we need to rotate sub matrix 12, 2 numbers ,each of the process 4 times, so we rotate 8 numbers in total. the middle will not be changed.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.