59 螺旋矩阵II
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> res(n, vector<int>(n, 0));
// 确定每一圈的起点(startx, starty)
int startx = 0, starty = 0;
// 确定遍历的圈数
// 计算方法:以第一圈为例,走完第一圈,第一行和最后一行都被遍历过,对称遍历
// 因此遍历完整的圈数量为n/2次
// 如果n是奇数,最后会剩下中心点mid未遍历,额外处理
int loop = n / 2;
// 我们规定每个圈分为四次遍历,每次遍历左闭右开区间(不包含每行/每列最后一个元素)
// offset表示右边界收缩个数
// 用于计算每行/每列遍历长度 n - offset
int offset = 1;
// count为待填充元素值
int count = 1;
while(loop--){
// 提前定义坐标,接下来遍历的时候,每次坐标计算都需要使用上一次坐标位置
int i = startx, j = starty;
// 上行遍历长度n - offset,遍历区间为[starty, n - offset)
// 这里条件为j < n - offset 因为是左闭右开区间
for(j; j < n - offset; j++){
res[i][j] = count++;
}
// 右列遍历长度n - offset,遍历区间为[startx, n - offset)
// 这里条件为i < n - offset 因为是左闭右开区间
for(i; i < n - offset; i++){
res[i][j] = count++;
}
// 下行遍历长度n - offset,遍历区间为[n - offset, starty)
// 这里条件为j > starty 因为是左闭右开区间
for(j; j > starty; j--){
res[i][j] = count++;
}
// 左列遍历长度n - offset,遍历区间为[n - offset, startx)
// 这里条件为i > startx 因为是左闭右开区间
for(i; i > startx; i--){
res[i][j] = count++;
}
// 遍历一圈完成,更新参数
// 更新下一个起点(沿右下对角线)
startx++;
starty++;
// 更新下一次遍历长度(每走一圈,遍历长度减1)
// 为什么减1: 因为每走一圈待遍历区间的左边界和右边界都会收缩
// offset表示待遍历区间的右边界收缩个数
// 我们的左边界永远不会被遍历,因为每次我们都设定左边界为新的startx/starty
// 因此只有右边界就被遍历过了,需要减1,对应offset + 1
offset++;
}
if(n % 2 != 0){
int mid = n / 2;
res[mid][mid] = count;
}
return res;
}
};
时间复杂度 \(O(n^2)\): 模拟遍历二维矩阵的时间
空间复杂度 \(O(1)\)