Saturday, March 7, 2015

54. Spiral Matrix Leetcode Java

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
For example,
Given the following matrix:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
You should return [1,2,3,6,9,8,7,4,5].
Solution:
Processing the element in spiral way.
I use a flags to realize the spiral order: up, right, bottom, left
as long as up<=bottom && left<=right, we have unprocessed elements.
Time complexity: O(n*n);
  public List<Integer> spiralOrder(int[][] matrix) {  
     List<Integer> res=new ArrayList<Integer>();  
     if(matrix==null || matrix.length==0 || matrix[0].length==0) return res;  
     int top=0;  
     int bottom=matrix.length-1;  
     int left=0;  
     int right=matrix[0].length-1;  
     int flag=0;  
     while(top<=bottom && left<=right){  
       switch(flag){  
         case 0: {  
           for(int i=left;i<=right;i++) res.add(matrix[top][i]);  
           top++;  
           flag=1;  
           break;  
         }  
         case 1:{  
           for(int i=top;i<=bottom;i++) res.add(matrix[i][right]);  
           right--;  
           flag=2;  
           break;  
         }  
         case 2:{  
           for(int i=right;i>=left;i--) res.add(matrix[bottom][i]);  
           bottom--;  
           flag=3;  
           break;  
         }  
         case 3:{  
           for(int i=bottom;i>=top;i--) res.add(matrix[i][left]);  
           left++;  
           flag=0;  
           break;  
         }  
         default: break;  
       }  
     }  
     return res;  
   }  

No comments:

Post a Comment