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:
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);
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