首页 > 代码库 > 每日算法之四十一：Spiral Matrix II （螺旋矩阵）

每日算法之四十一：Spiral Matrix II （螺旋矩阵）

2024-07-17 20:45:43   219人阅读

Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

For example,
Given n = 3,

You should return the following matrix:
[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

针对这个问题采用最直观的方式即可，即螺旋插入，这里有两个地方需要注意，一个是插入边界的界定，另一个就是辅助矩阵的开辟。
第一 个问题我们可以采用举例的方式，画一个4*4的矩阵，1-12这些数字插入进去是螺旋的一周，用数字标记插入的范围，再转化为和行数、矩阵规模n相关的表达式即可。
第二个问题使用O(n*n)的空间复杂度。
代码如下：
class Solution {
public:
    vector<vector<int> > generateMatrix(int n) {
        vector<vector<int> > matrix;
        if(n < 0)
            return matrix;
        int **m = new int*[n];
        for(int i = 0; i < n; i++)
        {
            m[i] = new int[n];
            memset(m[i], 0, sizeof(int)*n);
        }
        int currentnum = 1;
        int loop = 0;
        while(loop < (n+1)/2)
        {
            int tmp = n - 1 - loop;
            for(int i = loop; i <= tmp; i++)
                m[loop][i] = currentnum++;
            for(int i = loop + 1; i <= tmp; i++)
                m[i][tmp] = currentnum++;
            for(int i = tmp - 1; i >= loop; i--)
                m[tmp][i] = currentnum++;
            for(int i = tmp - 1; i >= loop + 1; i--)
                m[i][loop] = currentnum++;
            loop++;
        }
        for(int i = 0; i < n; i++)
        {
            vector<int> tmp;
            for(int j = 0; j < n; j++)
                tmp.push_back(m[i][j]);
            matrix.push_back(tmp);
        }
        for(int i = 0; i < n; i++)
            delete[] m[i];
        delete[] m;
        return matrix;
    }
};


联系
我们