跳转至

59 螺旋矩阵II

leetcode

思路参考

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)\)