leetcode 54. 螺旋矩阵

​
​

作者简介：C/C++ 、Golang 领域耕耘者，创作者
个人主页：作者主页
活动地址：CSDN21天学习挑战赛
题目来源： leetcode官网
如果感觉博主的文章还不错的话，还请关注➕ 、点赞👍 、收藏🧡三连支持一下博主哦~~~

💜 题目描述

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

示例1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

示例2：

输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]

🧡 算法分析

此题方法是用模拟题、语法题

首先 需要确定4个方向，如图：

按照题目意思， 需一直 →、↓、←、↑； →、↓、←、↑； 这个顺序来模拟遍历

算法步骤:

1. 定义四个方向的常数方向数组dx[]、dy[]，不妨假设 0 表示方向为向右，1 为向下，2 为向左，3 为向上。
2. 定义二维数组 st，代表该位置是否被访问过。
3. 从坐标 (0, 0) 开始，初始方向为 0。
4. 直接遍历n * m 个格子， 然后判断当前遍历的格子，是否超界，是否已经遍历，如果有，则改变方向；若无，继续遍历。

💚 代码实现

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> re;
        int n = matrix.size(); 
        if(!n) return re;
        int m = matrix[0].size();
        
        int dx[] = {0, 1, 0 , -1}, dy[] = {1, 0, -1, 0};
        vector<vector<bool>> st(n, vector<bool>(m));

        // d 表示方向
        for(int i = 0, x = 0, y = 0, d = 0; i < n * m; i ++)
        {
            re.push_back(matrix[x][y]);
            st[x][y] = true;

            int a = x + dx[d], b = y + dy[d];
            if(a < 0 || a >= n || b < 0 || b >= m || st[a][b])
            {
                // 说明不能走了
                d = (d + 1) % 4;
                a = x + dx[d], b = y + dy[d];
            }
            x = a, y = b;
        }

        return re;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

执行结果：

💙 时间复杂度分析

其中遍历一次， 时间复杂度为O(n * m)

如果觉得对你有帮助的话:
👍 点赞，你的认可是我创作的动力！
🧡 收藏，你的青睐是我努力的方向！
✏️ 评论，你的意见是我进步的财富！