| # |
Title |
Difficulty |
Topic |
| 59 |
Spiral Matrix II |
Medium |
Array |
Description
Given a positive integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.
Example:
1
2
3
4
5
6
7
|
Input: 3
Output:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]
|
Analyze
按顺序遍历，可以发现一次遍历包括4个步骤：
- 从左到右；
- 从上到下；
- 从右到左；
- 从下到上。
因此，大循环应该为遍历的几次，小循环为上述4个步骤。需要注意会发生重复遍历的地方，只有从右到左和从下到上可能会重复遍历。与59. Spiral Matrix II基本类似。
Submission
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class {
public int[][] generateMatrix(int n) {
int[][] res = new int[n][n];
int loop = 0, maxLoop = (n % 2 == 0) ? n / 2 : n / 2 + 1, cnt = 1;
while(loop < maxLoop) {
for(int j=loop; j<n-loop; j++)
res[loop][j] = cnt++;
for(int i=loop+1; i<n-loop; i++)
res[i][n-loop-1] = cnt++;
if(loop < n - loop - 1) {
for(int j=n-loop-2; j>=loop; j--)
res[n-loop-1][j] = cnt++;
for(int i=n-loop-2; i>loop; i--)
res[i][loop] = cnt++;
}
loop++;
}
return res;
}
}
|
Complex Analyze
时间复杂度为$$O(m times n)$$。
近期评论