精选50题之 54. 螺旋矩阵

心已赠人 2024-04-18 21:21 88阅读 0赞

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

*   *  原题目链接
     *  代码实现
     *  其他方式
     *  写在最后

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

给定一个包含 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\]

[参照][Link 2]

## 代码实现 ##

class Solution {
        
    public:
        vector<int> spiralOrder(vector<vector<int>>& matrix) {
        
            vector <int> ans;
            if(matrix.empty()) return ans; //若数组为空，直接返回答案
            int u = 0; //赋值上下左右边界
            int d = matrix.size() - 1;
            int l = 0;
            int r = matrix[0].size() - 1;
            while(true)
            {
        
                for(int i = l; i <= r; ++i) 
                    ans.push_back(matrix[u][i]); //向右移动直到最右
                if(++ u > d) 
                    break; //重新设定上边界，若上边界大于下边界，则遍历遍历完成，下同
                for(int i = u; i <= d; ++i) 
                    ans.push_back(matrix[i][r]); //向下
                if(-- r < l) 
                    break; //重新设定有边界
                for(int i = r; i >= l; --i) 
                    ans.push_back(matrix[d][i]); //向左
                if(-- d < u) 
                    break; //重新设定下边界
                for(int i = d; i >= u; --i) 
                    ans.push_back(matrix[i][l]); //向上
                if(++ l > r) 
                    break; //重新设定左边界
            }
            return ans;
        }
    };

复杂度分析：

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

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

## 其他方式 ##

某Python3 极简实现

class Solution:
        def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
            res = []
            while matrix:
                res += matrix.pop(0)
                matrix = list(map(list, zip(*matrix)))[::-1]
            return res

\[::-1\]翻转的过程是是可逆的，也可以用zip()实现。

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

## 写在最后 ##

中秋偷个懒

[Link 1]: https://leetcode-cn.com/problems/spiral-matrix/
[Link 2]: https://leetcode-cn.com/problems/spiral-matrix/solution/cxiang-xi-ti-jie-by-youlookdeliciousc-3/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/5147697c36ec478a901eb7bdb0499487.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/25c61a2335814be3b6c754e2a1631e5b.png