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

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

题目描述

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

数据范围

矩阵中元素数量 [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]

方法一:模拟 O(n2)


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


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


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


f7e21922aca54a2cb4cdd87a518c85e9.png

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


cc4b29080eeb4a5ca2c0cb7136fa8cc3.png


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


f2f213b3124d4c30ae568d6c4ccf9a02.png


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

73449d71136f444da0d6319fb4e75cd3.png



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



a9c089f4ba024f6f807238b034b174ed.png

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

e4d21108d36c46d2954fb719d8e9ace1.png


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;
    }
};

欢迎大家在评论区交流~

目录
相关文章
|
7月前
【一刷《剑指Offer》】面试题 20:顺时针打印矩阵
【一刷《剑指Offer》】面试题 20:顺时针打印矩阵
|
7月前
|
Java
每日一题《剑指offer》数组篇之顺时针打印矩阵
每日一题《剑指offer》数组篇之顺时针打印矩阵
62 0
每日一题《剑指offer》数组篇之顺时针打印矩阵
|
7月前
|
算法
算法题—顺时针打印矩阵
算法题—顺时针打印矩阵
54 0
|
7月前
剑指 Offer 29:顺时针打印矩阵
剑指 Offer 29:顺时针打印矩阵
42 0
|
7月前
|
Java
【剑指offer】-顺时针打印矩阵-19/67
【剑指offer】-顺时针打印矩阵-19/67
|
算法 C++
剑指offer(C++)-JZ29:顺时针打印矩阵(算法-模拟)
剑指offer(C++)-JZ29:顺时针打印矩阵(算法-模拟)
剑指offer_数组---顺时针打印矩阵
剑指offer_数组---顺时针打印矩阵
52 0
|
算法
算法练习题(七)——顺时针打印二维数组
算法练习题(七)——顺时针打印二维数组
114 0
|
Java C++
环形矩阵(螺旋矩阵)&&蛇形矩阵
环形矩阵(螺旋矩阵)&&蛇形矩阵
154 0
|
算法 前端开发 程序员
顺时针打印矩阵
顺时针打印矩阵
顺时针打印矩阵