题解 | #顺时针打印矩阵#

顺时针打印矩阵

http://www.nowcoder.com/practice/9b4c81a02cd34f76be2659fa0d54342a

描述

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

算法

图片说明
我们的目标是按照图中的数字大小顺序访问每个位置的值,然后按顺序保存每个点。

方法一

我们定义一个从 (0, 0) 出发的点,当遇到边界或者访问过的点之后就向右转,已经访问过的点就把它的值赋为一个不可能的值 inf。
如下图,我们访问到边界情况时就向右转
图片说明
如下图,当我们访问到 12 的下一个点的时候就向右转
图片说明
代码实现如下(python版代码注释参照c++版):

// c++
class Solution {
public:
    const int inf = 0x3f3f3f3f; // 访问过的值标记为 inf
    int x[4] = {0, 1, 0, -1}, y[4] = {1, 0, -1, 0}; // x, y 分别是行、列两个方向的向右换方向的顺序
    vector<int> printMatrix(vector<vector<int> > mat) {
        vector<int> res;
        int n = mat.size(), m = mat[0].size();
        int a = 0, b = 0, idx = 0;

        // 一共会访问 m * n 次,循环结束之后就代表所有点都访问过了一次
        for (int i = 0; i < m * n; i++) {
            res.push_back(mat[a][b]);
            mat[a][b] = inf; // 把访问过的值改成 inf
            int s = a + x[idx], t = b + y[idx]; // s, t 是下一个访问的值

            // 如果越界或者遇到访问过的值就需要换方向
            if (s < 0 || s >= n || t < 0 || t >= m || mat[s][t] == inf) {
                idx = (idx + 1) % 4; // 按照顺序改变遍历的方向
                s = a + x[idx], t = b + y[idx]; // 修正越界的 s, t 到合法的方向
            }
            a = s, b = t; // s, t 是合法的下一个访问节点
        }
        return res;
    }
};
# python3
class Solution:
    def printMatrix(self, mat):
        dir = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        inf = 0x3f3f3f3f
        i, j, idx = 0, 0, 0
        n, m = len(mat), len(mat[0])
        res = []
        for _ in range(n * m):
            res.append(mat[i][j])
            mat[i][j] = inf
            a, b = i + dir[idx][0], j + dir[idx][1]
            if a < 0 or a >= n or b < 0 or b >= m or mat[a][b] == inf:
                idx = (idx + 1) % 4
                a, b = i + dir[idx][0], j + dir[idx][1]
            i, j = a, b
        return res

因为我们把所有的节点都访问了一次,所以时间复杂度是 O(m * n)

方法二

方法二用python实现比较简单,其他语言不推荐使用。我们可以把原二维数组想象成一个木板,每次拆去四个方向的边框。
原来的样子
图片说明
拆去上方边框
图片说明
拆去右边边框
图片说明
直到二维矩阵消失。注意要判断每次拆去边框之前矩阵是否合法。

# python3
class Solution:
    # matrix类型为二维列表,需要返回列表
    def printMatrix(self, mat):
        res = []
        while mat:
            res += mat[0]
            mat.pop(0)
            if not mat or not mat[0]: break // 判断矩阵是否合法
            for i in range(len(mat)):
                res += [mat[i][-1]]
                mat[i].pop(-1)
            if not mat: break // 判断矩阵是否合法
            res += mat[-1][::-1]
            mat.pop(-1)
            if not mat or not mat[0]: break // 判断矩阵是否合法
            for i in range(len(mat) - 1, -1, -1):
                res += [mat[i][0]]
                mat[i].pop(0)
        return res

即使我们有的时候是直接弹出了整个一维数组,但是 append 实际上是复制了整个数组,所以最终我们的时间复杂度还是 O(m * n)。

全部评论

相关推荐

05-11 11:48
河南大学 Java
程序员牛肉:我是26届的双非。目前有两段实习经历,大三上去的美团,现在来字节了,做的是国际电商的营销业务。希望我的经历对你有用。 1.好好做你的CSDN,最好是直接转微信公众号。因为这本质上是一个很好的展示自己技术热情的证据。我当时也是烂大街项目(网盘+鱼皮的一个项目)+零实习去面试美团,但是当时我的CSDN阅读量超百万,微信公众号阅读量40万。面试的时候面试官就告诉我说觉得我对技术挺有激情的。可以看看我主页的美团面试面经。 因此花点时间好好做这个知识分享,最好是单拉出来搞一个板块。各大公司都极其看中知识落地的能力。 可以看看我的简历对于博客的描述。这个帖子里面有:https://www.nowcoder.com/discuss/745348200596324352?sourceSSR=users 2.实习经历有一些东西删除了,目前看来你的产出其实很少。有些内容其实很扯淡,最好不要保留。有一些点你可能觉得很牛逼,但是面试官眼里是减分的。 你还能负责数据库表的设计?这个公司得垃圾成啥样子,才能让一个实习生介入数据库表的设计,不要写这种东西。 一个公司的财务审批系统应该是很稳定的吧?为什么你去了才有RBAC权限设计?那这个公司之前是怎么处理权限分离的?这些东西看着都有点扯淡了。 还有就是使用Redis实现轻量级的消息队列?那为什么这一块不使用专业的MQ呢?为什么要使用redis,这些一定要清楚, 就目前看来,其实你的这个实习技术还不错。不要太焦虑。就是有一些内容有点虚了。可以考虑从PR中再投一点产出
点赞 评论 收藏
分享
04-29 22:35
门头沟学院 Java
牛友说改了名字能收到offer:旧图新发查看图片
点赞 评论 收藏
分享
评论
2
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务