Wednesday, August 26, 2015

[Matrix] Rotate Image

1. Example
rotate an 2D matrix by 90 degrees (clockwise)

[
[1,2,3],
[4,5,6],
[7,8,9]
]
==>
[
[7,4,1],
[8,5,2],
[9,6,3]
]

[
[1,   2,   3,  4]
[5,   6,   7,  8]
[9,  10,11,12]
[13,14,15,16]
]

2. Implementation
Complexity:Time: O(m*n) Space:O(1) in-place
keep 1
1->7[2,0]
7->9[,2,2]
9->3[0,2]
3->  1[0,0]

keep2
2->4[1,0]
4->8[2,1]
8->6[1,2]
6->  2 [0,1]
Q1: how many times?
A1: for n/2 layer, we do n/2 number of times rotate for each layer, they follow the same rule
Q1: how to iterate?
A1: we iterate to the element before boundary element (not included)
FOLLOW UP: What if a matrix nxm matrix, which means not square matrix?

// Time:O(m*n), Space:O(1)
public void rotate (int[][] matrix)
{



     // validate the input
     if ( matrix == null || matrix.length ==0 || matrix[0].length ==0)
     {
          return;
     }




     int layer = n >>1;
     for (int row = 0 ; row < layer; row++)
     {
          // NOTE:  col start from layer
          for (int col = row ; col < matrix[0].length-1;col++ )
          {     
                // NOTE: the first element for each layer (row index)
                // 4 value (4 corner) top<-left data-blogger-escaped--="" data-blogger-escaped--col="" data-blogger-escaped-1="" data-blogger-escaped-bottom="" data-blogger-escaped-col="" data-blogger-escaped-int="" data-blogger-escaped-matrix.legnth-1="" data-blogger-escaped-matrix="" data-blogger-escaped-right="" data-blogger-escaped-row="" data-blogger-escaped-temp="matrix[row][col];" data-blogger-escaped-top=""> 7 4 1, col has sth to do with row, cur ROW== next COL
                matrix[(matrix.length-1) - col][row] = matrix[(matrix.length-1)-row][(matrix.length-1) - col];//  e.g., 7 8 9 (bottom)-> 7 8 9(left), row has sth to do with col, cur ROW==next COL
                matrix[(matrix.length-1)-row][(matrix.length-1) - col] = matrix[col][(matrix.length-1)-row];// e.g., 3,6,9 => 9,6,3, col ~ row, cur ROW==next COL
                matrix[col][(matrix.length-1)-row] = temp;// 1,2,3(top)->1,2,3(right)
          }
     }



}
// 1234 // 5678 //=> // 51 // 62 // 73 // 84
public int[][] rotate(int[][] matrix)
{
    // NOTE: there is no way to do in-place, so create a new matrix
    int[][] newmatrix = new int[matrix[0].length][mtrix.length];
    // validate the input
    if ( matrix == null || matrix.length ==0 || martix[0].length == 0)
         return newmatrix;

   
    
    for (int i = 0; i < matrix.length; i++)
        for (int j = 0 ; j < matrix[0].length; j++)
              newmarix[j][(matrix.length-1) - i] = matrix[i][j];
    return newmatrix;
}
3. Similar Ones
Spiral Matrix I
Spiral Matrix II
http://www.careercup.com/question?id=5667482614366208

No comments:

Post a Comment