螺旋矩阵
一道经典的二维数组循环题目，难点是边界值的把握
对应题目59. 螺旋矩阵 II?
模拟法
螺旋矩阵的产生步骤大致为这3步。
- 先判断需要螺旋几次，给出结论需要螺旋\(\frac{n}{2}\)次
- 对于四条边的一个循环遍历
- 判断\(n\)的奇偶性，如果为奇数最后再循环终点即矩阵中心填上\(n \times n\)
由于难点是边界值的控制，所以这里首先要确定区间，这里使用的区间为前闭后开的区间。分析复杂度，由于矩阵的每个节点都需要遍历到，所以时间复杂度为\(O(n^2)\)，同样的由于需要开辟出一个\(n \times n\)的矩阵所以空间复杂度为\(O(n^2)\)。
vector<vector<int>> generateMatrix(int n) {
// define a two-dimensional array matrix.
vector<vector<int>> matrix(n,vector<int>(n));
// offSet defined is used to control boundary.
int x = 0,y = 0,startX = 0,startY = 0,offSet = 1,count = 1;
// the number of cycles is less than n/2.
int times = 0;
while (times < n/2) {
for (;x < n - offSet;x ++)
matrix[y][x] = count ++;
for (;y < n - offSet;y ++)
matrix[y][x] = count ++;
for (;x > startX;x --)
matrix[y][x] = count ++;
for (;y > startY;y --)
matrix[y][x] = count ++;
x = ++startX;y = ++startY;
offSet ++;
times ++;
}
// use binary AND operation to determine odd or even of the n.
if (n & 1)
matrix[x][y] = count;
return matrix;
}