问题
Given a positive integer n, generate an n x n matrix filled with elements from 1 to n2 in spiral order.
Example 1:
Input: n = 3
Output: [[1,2,3],[8,9,4],[7,6,5]]
Example 2:
Input: n = 1
Output: [[1]]
Constraints:
- 1 <= n <= 20
思考
转方向就好了.
方法1
时间复杂度 O ( n 2 ) O(n^2) O(n2).
空间复杂度O(1).
class Solution {
public int[][] generateMatrix(int n) {
int left = 0, right = n - 1, top = 0, bottom = n - 1;
int val = 1, max = n * n;
int x = 0, y = -1;
int[][] res = new int[n][n];
while(val <= max){
y++;
while(y <= right){
res[x][y++] = val++;
}
top++;
y--;
x++;
while(x <= bottom){
res[x++][y] = val++;
}
right--;
x--;
y--;
while(y >= left){
res[x][y--] = val++;
}
bottom--;
y++;
x--;
while(x >= top){
res[x--][y] = val++;
}
left++;
x++;
}
return res;
}
}
方法2
更简洁的写法.
时间复杂度 O ( n 2 ) O(n^2) O(n2).
空间复杂度O(1).
class Solution {
static int[][] moves = new int[][]{{0,1},{1,0},{0,-1},{-1,0}};
public int[][] generateMatrix(int n) {
int[][] res = new int[n][n];
int cur = 1;
for(int i = 0; i <= n/2; i++){
for(int j = i; j < n-i; j++)
res[i][j] = cur++;
for(int j = i+1; j < n-i; j++)
res[j][n-i-1] = cur++;
for(int j = n-i - 2; j >= i ; j--)
res[n-i-1][j] = cur++;
for(int j = n-i-2; j > i ; j--)
res[j][i] = cur++;
}
return res;
}
}