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
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/299518.html
標籤：java
上一篇：Java中的類和物件