1、题目
给你一个正整数 n ，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
示例 1：
输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]
示例 2：
输入：n = 1
输出：[[1]]
提示：
1 <= n <= 20
2、思路
(模拟) O ( n 2 ) O(n^2) O(n2)
给定一个正整数n，让我们生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
样例：
如样例所示，n = 3 , 我们输出[[1,2,3],[8,9,4],[7,6,5]]，下面来讲解模拟的做法。
具体过程如下：
1、我们顺时针定义四个方向：上右下左。d = 0表示向右走，d = 1表示向下走，d = 2表示向左走，d = 3表示向上走，方向偏移数组定义为 dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0}，如下图所示：
2、当前位置定义为(x,y)，使用d = (d + 1) % 4来更改方向，那么下个要走的位置(a, b)则表示为： a = x + dx[d], b = y + dy[d]。
3、从左上角开始遍历，先往右走，走到不能走为止，然后更改到下个方向，再走到不能走为止，依次类推，遍历 n 2 n^2 n2 个格子后停止。
时间复杂度分析： 矩阵中的每个数都被遍历一次，因此时间复杂度为 O ( n 2 ) O(n^2) O(n2)， n n n是给定的正整数。
3、c++代码
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>>res(n, vector<int>(n, 0));
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0}; //方向偏移数组
int x = 0, y = 0; //当前位置
for(int i = 1, d = 0; i <= n*n; i++)
{
res[x][y] = i;
int a = x + dx[d], b = y + dy[d];
if(a <0 || a == n || b < 0 || b == n || res[a][b]){ //出界或者该位置已经被走过
d = (d + 1) % 4; //更改方向
a = x + dx[d], b = y + dy[d]; //下一个要走的位置
}
x = a, y = b;
}
return res;
}
};
4、java代码
class Solution {
public int[][] generateMatrix(int n) {
int[][] res = new int[n][n];
int[] dx = {0, 1, 0, -1}, dy = {1, 0, -1, 0}; //方向偏移数组
int x = 0, y = 0; //当前位置
for(int i = 1, d = 0; i <= n*n; i++)
{
res[x][y] = i;
int a = x + dx[d], b = y + dy[d];
if(a <0 || a == n || b < 0 || b == n || res[a][b] != 0){ //出界或者该位置已经被走过
d = (d + 1) % 4; //更改方向
a = x + dx[d] ;
b = y + dy[d]; //下一个要走的位置
}
x = a;
y = b;
}
return res;
}
}
原题链接： 59. 螺旋矩阵 II
