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].
Idea: Brute force. The left up corner and the bottom right corner of the i'th spiral is (0+i, 0+i) and (m-1-i, n-1-i), where i starts from 0.
The only special case is when there is only one row or only one column, the spiral will not goes back to the start point.
Time: O(m*n) Space: O(1)
Code:
public class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> result=new ArrayList<Integer>();
if(matrix.length==0||matrix[0].length==0)
return result;
int startI=0;
int startJ=0;
int endI=matrix.length-1;
int endJ=matrix[0].length-1;
while(startI<=endI&&startJ<=endJ)
{
if(startI==endI)
{
for(int j=startJ;j<=endJ;j++)
result.add(matrix[startI][j]);
break;
}
if(startJ==endJ)
{
for(int i=startI;i<=endI;i++)
result.add(matrix[i][startJ]);
break;
}
for(int j=startJ;j<=endJ;j++)
result.add(matrix[startI][j]);
for(int i=startI+1;i<=endI;i++)
result.add(matrix[i][endJ]);
for(int j=endJ-1;j>=startJ;j--)
result.add(matrix[endI][j]);
for(int i=endI-1;i>startI;i--)
result.add(matrix[i][startJ]);
startI++;
startJ++;
endI--;
endJ--;
}
return result;
}
}
No comments:
Post a Comment