O(3/4*n^2), c++ easy understanding, i think it maybe faster than O(1*n^2) method


  • 0
    J
    //  divide origin matrix into 4 part, left swap 3 times
    //  n%2 == 1?
    //  n%2=0
    //  y y x x      z z x x    z z x x     z z y y
    //  y y x x      z z x x    z z x x     z z y y
    //  z z w w   => y y w w => w w y y  => w w x x
    //  z z w w      y y w w    w w y y     w w x x
    //
    //  n%2=1
    //  y y y x x       z z z x x    z z z x x     z z z y y
    //  y y y x x       z z z x x      z z z x x     z z z y y
    //  z z t x x =>  y y t x x => w w t x x =>  w w t y y
    //  z z w w w    y y w w w    w w y y y     w w x x x
    //  z z w w w    y y w w w    w w y y y     w w x x x
    
    
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        
        for( int i = 0 ; i <= n/2-1; i++)
            for(int j = 0; j <= (n-1)/2; j++)
                matrix[i][j] ^= matrix[n-1-j][i] ^= matrix[i][j] ^= matrix[n-1-j][i];
        
        for( int i = n/2 ; i <= n-1; i++)
            for(int j = 0; j <= n/2-1; j++)
                matrix[i][j] ^= matrix[n-1-j][i] ^= matrix[i][j] ^= matrix[n-1-j][i];
        
        for( int i = (n+1)/2 ; i <= n-1; i++)
            for(int j = n/2; j <= n-1; j++)
                matrix[i][j] ^= matrix[n-1-j][i] ^= matrix[i][j] ^= matrix[n-1-j][i];
        
    }
    
    //divide along diagonals, then rotate right
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        int temp;
        for( int i = 0 ; i <= n/2; i++){
            for(int j = i; j < n-i-1; j++){
                temp = move(matrix, matrix[i][j], j, n-1-i);
                temp = move(matrix, temp, n-1-i, n-1-j);
                temp = move(matrix, temp, n-1-j, i);
                move(matrix, temp, i, j);
            }
        }
        
    }
    
    int move(vector<vector<int>>& matrix, int a, int i, int j){
        int temp = matrix[i][j];
        matrix[i][j] = a;
        return temp;
    }

Log in to reply
 

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