Tuesday, September 1, 2015

[Matrix] Spiral Matrix

1. Example
Spiral Matrix I "print out"
Return all elements of the matrix in spiral order
matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
]
You should return [1,2,3,6,9,8,7,4,5]

2. Implementation
Q1: spiral order?
A1: top->right->bottom->left and layer
Q1: layer , layer = max(m,n)
3X5 matrix, layer =5/2 =2
12345
67890
32456
layer 1: 123450654236
layer 2: 789 start from layer 2, top->right
5X3 matrix, layer =5/2 =2
123
456
789
064
235
layer 1: 123694532074
layer2: 586 start from layer 2
Q1: how to define 123 69 or 12 36 98
A1: I mean the start position of each direction, we move to len -2 and next direction start from index
Q1: layer 1 [0,layer1],[0,1< len-1],    [0,2],[1< len-1,2]   [2,len-1][2,len-2],    [len-1][0],[len-2][0]
A1: so layer 2 [layer1, layer1]

//[[1,2,3,4,5,6,7,8,9,10]] 1x10 matrix, layer 10/2 =5??? or 1ayer 1/2 =0 

 //int size = Math.max(matrix.length, matrix[0].length);
 int size = Math.min( matrix.length, matrix[0].length );

// NOTE:
if (size%2 ==1) { 
for (int i = size/2; i < matrix.length -size/2;i++) {
   for (int j = size/2; j < matrix[0].length - size/2; j++) { 
       res.add(matrix[i][j]); 
   } 
}
// Time:O(m*n), Space:O(m*n) an m*n array

public List spiralOrder (int[][] matrix)
{




      List res = new ArrayList();




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




      // NOTE:Runtime Error Message:
      //Line 28: java.lang.ArrayIndexOutOfBoundsException: 1
      //Last executed input:
      //[[1,2,3,4,5,6,7,8,9,10]] 1x10 matrix, layer 10/2 =5??? or 1ayer 1/2 =0 
      //int size = Math.max(matrix.length, matrix[0].length);
      int size = Math.min( matrix.length, matrix[0].length );
      for (   int level = 0; level < size/2 ;level++)
      {

            // top, col iterate
            for (int j = level; j < matrix.length[0]-1-level; j++)
                  res.add( matrix[level][j] );
            // right, row iterate
            for (int k = level; k < matrix.length -1-level ; k++)
                  res.add(  matrix[k][matrix[0].length-1-level] );
            // bottom, col iterate
            for (int j = matrix[0].length-1-level; j >level; j--)
                  res.add( matrix[matrix.length-1-level][j]  );
            // left, row iterate
            for (int k = matrix.length-1-level; k > level; k--) 
                  res.add( matrix[k][level] );
      }






      if (size%2 ==1)
      {
            for (int i = size/2; i < matrix.length -size/2;i++)
            {
                 for (int j = size/2; j < matrix[0].length - size/2; j++)
                 {
                       res.add(matrix[i][j]);
                 }
            }
            /*
            // column size > row size 5x9
            if ( matrix.length < matrix[0].length )
            {
                for ( int i = levelNum; i < matrix[0].length - levelNum ; i++)
                {
                    result.add(matrix[levelNum][i]);
                }
            }
            // row size > column size 9X5
            else 
            {
                for ( int i = levelNum ; i < matrix.length - levelNum; i++)
                {
                    result.add(matrix[i][levelNum]);
                }
            }
            */
      }
        
     


      return res;



}
[1,2,3],
[4,5,6],
[7,8,9]
size = 3 layer =3/2 =1
for (i=0 i<1 data-blogger-escaped-2="" data-blogger-escaped-for="" data-blogger-escaped-j="3-1-0;j" data-blogger-escaped-k="">0;j--)
    for (k = 3-1-0; k>0;k--)
if (size%2==1)
     for (i= size/2;i< len-size/2;)  1; 3-1 count to end
         for (j=size/2; j < len-size/2) 3-1 count to end


3. Similar Ones

Spiral Matrix II
Set Matrix Zero
Rotate Image

No comments:

Post a Comment