数组05–螺旋矩阵Ⅱ

59. Spiral Matrix II

描述

给定一个正整数 n，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。

示例:

输入: 3

输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ]

思路

本题并不涉及到什么算法，就是模拟过程，考察对代码的掌控能力。如何画出这个螺旋排列的正方形矩阵呢？

很多同学刚开始做这种题目的时候，上来就是一波判断猛如虎。

结果运行的时候各种问题，然后开始各种修修补补，最后发现改了这里那里有问题，改了那里这里又跑不起来了。

求解本题依然是要坚持循环不变量原则。

模拟顺时针画矩阵的过程:

• 填充上行，从左到右；
• 右列，从上到下；
• 下行，从右到左；
• 左列，从下到上；

要画每四条边，这四条边怎么画，每画一条边都要坚持一致的左闭右开，或者左开右闭的原则，这样这一圈才能按照统一的规则画下来。

Solution

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n, vector<int>(n, 0)); //使用vector定义一个二维数组
        int startx = 0, starty = 0; //循环一个圈的起始位置
        int loop = n / 2;  // 循环几个圈，
        int mid = n / 2;  //矩阵中间的位置，比如，n=3时，中心点为(1,1)
        int count = 1; // 用来给矩阵中每一个格子赋值
        int offset = 1; // 控制每一条边遍历的长度，每次循环右边界收缩一位
        int i, j;
        
        while (loop --) {
            i = startx;
            j = starty;
            
            // 四个for循环模拟四条边转圈
            for (j = starty; j < n - offset; j++) {
                res[startx][j] = count++;
            }
            
            for (i = startx; i < n - offset; i++) {
                res[i][j] = count++;
            }
            
            for (; j > starty; j--) {
                res[i][j] = count++;
            }
            
            for (; i > startx; i--) {
                res[i][j] = count++;
            }
            
            // 第二圈开始的时候，起始位置各自加一
            startx++;
            starty++;
            
            offset += 1;
        }
        
        // 当n为奇数时，需要单独给最后中心值赋值
        if(n % 2) {
            res[mid][mid] = count;
        }
        return res;
    }
};

相关题目

• 54.螺旋矩阵
• 剑指Offer 29.顺时针打印矩阵