美文网首页
面试题29.顺时针打印矩阵_hn

面试题29.顺时针打印矩阵_hn

作者: 1只特立独行的猪 | 来源:发表于2020-03-31 22:13 被阅读0次

题目描述

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

示例

示例 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]

限制:

0 <= matrix.length <= 100
0 <= matrix[i].length <= 100

解答方法

方法一:

思路

https://leetcode-cn.com/problems/shun-shi-zhen-da-yin-ju-zhen-lcof/solution/mian-shi-ti-29-shun-shi-zhen-da-yin-ju-zhen-she-di/

代码

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        m = len(matrix)
        if m == 0:
            return []
        n = len(matrix[0])
        
        l = 0
        r = n - 1
        t = 0
        b = m - 1
        res = []
        while True:
            for i in range(l, r+1):
                res.append(matrix[t][i])
            t += 1
            if t>b:break
            for i in range(t, b+1):
                res.append(matrix[i][r])
            r -= 1
            if l>r:break
            for i in range(r, l-1,-1):
                res.append(matrix[b][i])
            b -= 1
            if b<t:break
            for i in range(b, t-1, -1):
                res.append(matrix[i][l])
            l += 1
            if l > r:break
        return res

时间复杂度

O(MN) : M,NM,N 分别为矩阵行数和列数。

空间复杂度

O(1) : 四个边界 l , r , t , b 使用常数大小的 额外 空间( res 为必须使用的空间)

相关文章

网友评论

      本文标题:面试题29.顺时针打印矩阵_hn

      本文链接:https://www.haomeiwen.com/subject/ksyuuhtx.html