Tuesday, June 09, 2015

Rotating an NxN Matrix 90 Degrees

If space has no limit, rotating it while copying it. This is On^2) in speed.

For in-place rotating, which is memory economy, imaging matrix is divided to layers and edges in each layer is moving clock wise. This is O((n/2)*(n/2-1)!)

 package a.ma;  

 public class MatrixRotate {
      public static void main(String[] args) {
           int ma[][] = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 },
                     { 13, 14, 15, 16 } };
           printArray(ma);
           //rotate(ma, 4);
            copyRotate(ma,4);
           //printArray(ma);
      }
      public static void printArray(int[][] matrix) {
           System.out.println(matrix.length);
           for (int i = 0; i < matrix.length; i++) {
                for (int j = 0; j < matrix.length; j++)
                     System.out.print(matrix[i][j]);
                System.out.println();
           }
      }
 /**
  * based on simple conversion that rows become columns
  * first row becomes last column, second row become last second column...
  * element wise, first one become  
  * @param matrix
  * @param n
  */
      public static void copyRotate(int[][] matrix, int n) {
           int tmp[][] = new int[n][n];
           for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++)
                     tmp[i][j] = matrix[n - j - 1][i];
           }
           printArray(tmp);
      }
 /**
  * 1111
  * 2222
  * 3333
  * 4444
  * imagine there is a center, the ractangle rotate around the center.
  * there are n/2 circles/layers without counting the center point, if n is odd number, the center point is not moving
  * so there will be 1=n/2 layers to move, for each layer
  * top edge, except last corner, will move to right edge
  * right edge, except last corner, will move to bottom edge
  * bottom edge, except last corner, will move to left edge
  * left edge, except last corner will move to top edge
  *  
  * to do the moving, use a variable to hold the variable that is going to be overridden, assign it back to proper
  * position after a layer's moving
  *  
  * in this algorithm, (x,x) is the element chosen to be first element in a layer to move, x is up to n/2-1 (counting from 0)
  *  
  * to do the moving, first loop is for all the layers, which is 0..n/2-1  
  * in each layer, elements need to move is between first and last. first is [x,x], then last should be [x,n-1-layer-1]
  * a variable cursor is used to move between first and last
  * @param matrix
  * @param n
  */
      public static void inPlaceRotate(int[][] matrix, int n) {
           //first loop is for all the layers, which is 0..n/2-1  
           for (int layer = 0; layer < n / 2; ++layer) {
                int first = layer;//first is [x,x] so it always be [layer,layer]
                //last here means last element of an edge in a layer, which is not part of moving element
                //for example, first layer top line, the element to move is 1 1 1
                int last = n - 1 - layer ;
                for (int i = first; i < last; ++i) {
                     int cursor = i - first;//sequence of moving element
                     //do the element movement based on top edge
                     int top = matrix[first][i]; // save top element
                     // then move left up to top
                     matrix[first][i] = matrix[last - cursor][first];
                     // then move bottom to left
                     matrix[last - cursor][first] = matrix[last][last - cursor];
                     // then move right to bottom
                     matrix[last][last - cursor] = matrix[i][last];
                     // finally put original top element to right edge
                     matrix[i][last] = top;  
                }
           }
      }
 }

No comments: