精选50题之 59. 螺旋矩阵 II

古城微笑少年丶 2024-04-18 23:30 75阅读 0赞

### 腾讯精选练习（50 题）之 59. 螺旋矩阵 II ###

*   *  原题目链接
     *  直接实现
     *  题目分析
     *  其他方式

## [原题目链接][Link 1] ##

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

> 示例:  
> 输入: 3  
> 输出:  
> \[  
> \[ 1, 2, 3 \],  
> \[ 8, 9, 4 \],  
> \[ 7, 6, 5 \]  
> \]

## 直接实现 ##

这道题和昨天的 [精选50题之 54. 螺旋矩阵][50_ 54.] 问题背景一致，且互为逆命题。进行简单的修改就可以实现。

class Solution {
        
    public:
        vector<vector<int>> generateMatrix(int n) {
        
            //定义输出二维矩阵为 n*n
            vector<vector<int>> res(n);
            for(int i =0; i < res.size(); i++)
                res[i].resize(n); // 列大小的重新定义
            // vector<vector<int>> res(n, vector<int>(n)); 
                
            // 定义上下左右的初始边界
            int l = 0;
            int r = n-1;
            int u = 0;
            int d = n-1;
            // 定义初始数字
            int num = 1;
            
            while(true)
            {
        
                //左——>右
                for(int i = l; i <= r; i++)
                    res[u][i] = num++;
                if(u++ >= d) break;
                //上——>下
                for(int i = u; i <= d; i++)
                    res[i][r] = num++;
                if(r-- <= l) break;
                //右——>左
                for(int i = r; i >= l; i--)
                    res[d][i] = num++;
                if(d-- <= u) break;
                //下——>上
                for(int i = d; i >= u; i--)
                    res[i][l] = num++;
                if(l++ >= r) break;
            }
            return res;
        }
    };

复杂度分析：

*  时间复杂度：O(N^2)
 *  空间复杂度：O(N^2)

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70]

## 题目分析 ##

还是有必要写一点分析。以防冷不丁一看想不起来?

其实无论称其为“模拟过程” 还是 “洋葱遍历（填充）”，本质是一样的。都是先生成一个空矩阵，然后由外向内逐个填充。依据的规则，首先要设定边界，接着每一个方向填完后，要更新边界（向内收缩），至于迭代条件/循环终止判断，既可以预先设置（num <= n\*n），也可以通过判断是否即将发生越界判断（e.g. if(l++ >= r) break;）。

图胜于言  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70 1]

## 其他方式 ##

一、结构上的简化  
区别在于对二维矩阵的理解，很巧妙  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70 2]

class Solution {
        
    public:
        vector<vector<int>> generateMatrix(int n) {
        
            vector<vector<int>> res(n, vector<int>(n));
        for(int s = 0, e = n - 1, m = 1; s<=e ; s++,e--){
        
            if(s==e) res[s][e] = m++;
            for (int j = s; j <= e-1; j++) res[s][j] = m++;
            for (int i = s; i <= e-1; i++) res[i][e] = m++;
            for (int j = e; j >= s+1; j--) res[e][j] = m++;
            for (int i = e; i >= s+1; i--) res[i][s] = m++;
        }
        return res;
        }
    };

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70 3]

二、Python内置方法快速实现逆过程  
昨天的 [精选50题之 54. 螺旋矩阵][50_ 54.] 最后有一个Python3的极短实现，本题也有一种?  
[benjy 的回答][benjy]

class Solution:
        def generateMatrix(self, n):
            ans = [[0] * n for _ in range(n)]
            x, y, dx, dy = 0, 0, 0, 1
            for i in range(1, n * n + 1):
                ans[x][y] = i
                if ans[(x + dx) % n][(y + dy) % n] > 0:
                    dx, dy = dy, -dx
                x, y = x + dx, y + dy
            return ans

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70 4]

[Link 1]: https://leetcode-cn.com/problems/spiral-matrix-ii/
[50_ 54.]: https://blog.csdn.net/weixin_41728431/article/details/100751702
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/7a6b1958bda648d5b025c6795527f0a6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/5244a263ca334d94a2d6a174f1190fb6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/739e26bab63147518673eb21d5114ef2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/9a3109a4a0b442f8b22c32cd74a15328.png
[benjy]: https://leetcode-cn.com/problems/spiral-matrix-ii/solution/qiao-miao-pan-duan-he-shi-zhuan-xiang-_shi-jian-fu/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70 4]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/5982b6685bf34312b38e527015a94a10.png