剑指offer 28. 顺时针打印矩阵

✍个人博客：https://blog.csdn.net/Newin2020?spm=1011.2415.3001.5343
📚专栏地址：剑指offer系列题解
📝原题地址：题目地址
📣专栏定位：为找工作的小伙伴整理常考算法题解，祝大家都能成功上岸！
❤️如果有收获的话，欢迎点赞👍收藏📁，您的支持就是我创作的最大动力💪

题目描述

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

数据范围

矩阵中元素数量 [0,400]。

样例

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

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

方法一：模拟 O(n²)

我们可以模拟顺时针查找，遍历所有点并且按照一定方向一直探索，直到数组越界或该位置已经遍历过再改变方向。

我们拿题目样例进行举例，看看是怎么执行的：

第一趟遍历： $[1,2,3,4]$

第二趟遍历： $[1,2,3,4,8,12]$

第三趟遍历： $[1,2,3,4,8,12,11,10,9]$

第四趟遍历： $[1,2,3,4,8,12,11,10,9,5]$

第五趟遍历： $[1,2,3,4,8,12,11,10,9,5,6,7]$

得到最终数组： $[1,2,3,4,8,12,11,10,9,5,6,7]$

class Solution {
public:
    vector<int> printMatrix(vector<vector<int> > matrix) {
        vector<int> ans;
        if (matrix.empty())  return ans;
        int n = matrix.size(), m = matrix[0].size();
        int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };
        vector<vector<bool>> st(n, vector<bool>(m, false));	//状态数组
        int x = 0, y = 0, d = 0;
        for (int i = 0; i < n * m; i++)
        {
            ans.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 ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

欢迎大家在评论区交流~