[59. Spiral Matrix II]
[(https://leetcode.cn/problems/spiral-matrix-ii/)
螺旋矩陣
- 其實此題并沒有設計什么靈活的演算法，只是對模擬的要求高，本題需要考慮的邊界條件比較多，因此需和之前所講的Binary Search的一樣，依舊需要遵循回圈不變數原則，也就是左閉右開
- 模擬矩陣：由外向內
- 上行從左往右
- 右列從上往下
- 下行從右往左
- 左列從下到上
- 代碼如下：
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
int loop = n / 2; //遍歷圈數
int startx = 0, starty = 0; //每次遍歷開始的位置
int offset = 1; //限制遍歷的長度，每新增一圈需要減一
int number = 1; //為矩陣賦值
int i = 0, j = 0; //i為y，j為x以此模擬
vector<vector<int>>result( n, vector<int>( n, 0 ) ); //結果矩陣
while(loop-- != 0)
{
//遍歷左閉右開
//上行從左到右
for(i = starty ; i < n - offset; ++i )
{
result[startx][i] = number++;
}
//左列從上到下
for(j = startx ; j < n - offset; ++j )
{
result[j][i] = number++;
}
//下行從右到左
for( ; i > starty; --i )
{
result[j][i] = number++;
}
//左列從下到上
for( ; j > startx; --j )
{
result[j][i] = number++;
}
//每遍歷完一圈，起始位置的x，y都需要加一，以此準備下一圈
++startx;
++starty;
//控制遍歷長度
++offset;
}
//若n為奇數，矩陣最中間的數我們并沒有遍歷，因此還需要賦值
if( n % 2 == 1 )
{
result[startx][starty] = number;
}
return result;
}
};
-
時間復雜度：O（n2）
空間復雜度：O（n2）
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/514098.html
標籤：其他