For example,
Given n = 3,
You should return the following matrix:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]
Idea: First initialize the n*n matrix. Then fill each of the spirals with a self-increasing counter (counter++). The top left corner of the i'th spiral is (0+i, 0+i), the bottom right corner of the i'th spiral is (n-1-i, n-1-i), where i starts from 0. There is a special case that the last spiral may be just one row or one column that the pointer should not come back.
Time: O(n^2) Space: O(1)
Code:
public class Solution {
public int[][] generateMatrix(int n) {
int[][] matrix=new int[n][n];
int counter=1;
int startI=0;
int startJ=0;
int endI=n-1;
int endJ=n-1;
while(startI<=endI&&startJ<=endJ)
{
if(startI==endI)
{
for(int j=startJ;j<=endJ;j++)
matrix[startI][j]=counter++;
break;
}
if(startJ==endJ)
{
for(int i=startI;i<=endI;i++)
matrix[i][startJ]=counter++;
break;
}
for(int j=startJ;j<endJ;j++)
matrix[startI][j]=counter++;
for(int i=startI;i<endI;i++)
matrix[i][endJ]=counter++;
for(int j=endJ;j>startJ;j--)
matrix[endI][j]=counter++;
for(int i=endI;i>startI;i--)
matrix[i][startJ]=counter++;
startI++;
startJ++;
endI--;
endJ--;
}
return matrix;
}
}
No comments:
Post a Comment