Leetcode 54. 螺旋矩阵(C++) （小白学习之路）

ゝ一世哀愁。 2023-07-13 15:12 7阅读 0赞

最近忙着做项目实训，刷题的时间少了，代码写起来就有点手生，看来每天代码都不能少写啊。

题目描述：

给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。

示例 1:

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

输入:  
\[  
  \[1, 2, 3, 4\],  
  \[5, 6, 7, 8\],  
  \[9,10,11,12\]  
\]  
输出: \[1,2,3,4,8,12,11,10,9,5,6,7\]

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/spiral-matrix  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这题思路也不难想，起初我又想到了递归，结果发现递归方法只适用于n\*n的方阵，从上次做的对角线矩阵得到的启发，就是确定行走方向一个一个输出，这题的方向比对角线更好写，设定上下左右四个边界up,down,left,right, 行走完就是up++或者down--， 列走完就是left++或者right--，循环结束的条件是up>down或者left>right，代码如下：

class Solution {
    public:
        vector<int> spiralOrder(vector<vector<int>>& matrix) {
            if(!matrix.size()) return {};           //矩阵为空直接返回{}
            int M = matrix.size();
            int N = matrix[0].size();
            vector<int> res;
            int up=0,down=M-1,left=0,right=N-1;     //设置四个边界
            while(up<=down&&left<=right)           //出边界的条件
            {
                for(int j=left;j<=right;j++) res.push_back(matrix[up][j]);
                up++;                              //上面一行遍历完up++
                if(up>down) break;                //应对循环起始up==down的情况
                for(int i=up;i<=down;i++) res.push_back(matrix[i][right]);
                right--;                          //右边一列遍历完right--
                if(right<left) break;            //应对循环起始left==right的情况
                for(int j=right;j>=left;j--) res.push_back(matrix[down][j]);
                down--;                //这里无需做出判断，因为up==down的情况在up++那里已经判断过
                for(int i=down;i>=up;i--) res.push_back(matrix[i][left]);
                left++;
            }
            return res;
    
        }
    };

时间和空间是C++代码平均水平，逛了一遍解答区发现大家思路基本差不多，这里时间复杂度O（m\*n）,空间复杂度O（1），这里有个有意思的地方，一开始没有判断 if(up>down) break;这一行，会出现奇数行矩阵中间一行重复输出的情况，于是加了这个判断，我看到有的题解里给4个方向结束都做了判断，其实不必，只需前两个即可，这里应对的情况就是一开始up==down或者left==right，当第一次判断成立后，后面都会在for循环和while循环的条件判断中再判断一次，因此可以少写两行。程序员嘛，提升效率的同时还能节省体力，两全其美！

在逛题解的时候发现了一个大神的python答案，思路很清晰，代码现在还有点看不懂，希望自己后面代码能力提升的时候能读懂。贴上大神的代码如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01pbnQyeXg0_size_16_color_FFFFFF_t_70][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01pbnQyeXg0_size_16_color_FFFFFF_t_70]: /images/20230529/1b068f1f5c0e4dd8b971d872d3ea9f66.png