LVS CANopen reference jquery遍历子元素 jquery去掉空格 jquery获取下一个元素 jquery关闭当前窗口 sallenkey滤波器 xcode打包 docker创建容器 python多线程 java自学教程 java时间格式 java框架学习 小程序源码下载 咪咕客户端下载 电脑手机模拟器 网络克隆 英雄联盟体验服转换器 wscript 算法笔记 天正建筑2007 只狼台词 绘图软件下载 开源即时通讯软件 win7仿win8主题 非凡资源搜索器 小米自动开关机 强制换行快捷键 cdr群组快捷键 生成海报 total同级生2下载 方正倩体 csshover php递归函数 制表符 excel工作表下载 标记宏 created 方正正准黑简体
当前位置: 首页 > 学习教程  > python

【Leetcode】54.螺旋矩阵(Spiral Matrix)

2021/2/7 22:55:30 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

No54.螺旋矩阵 题目 给定一个包含 m x n 个元素的矩阵(m 行, n 列),请按照顺时针螺旋顺序,返回矩阵中的所有元素。 示例1 输入: [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ]输出: [1,2,3,6,9,8,7,4,5] 示例2 输入: [ [1, 2,…

No54.螺旋矩阵

题目

给定一个包含 m x n 个元素的矩阵(m 行, n 列),请按照顺时针螺旋顺序,返回矩阵中的所有元素。

示例1

  • 输入:
    [
    [ 1, 2, 3 ],
    [ 4, 5, 6 ],
    [ 7, 8, 9 ]
    ]
  • 输出: [1,2,3,6,9,8,7,4,5]

示例2

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

解题代码(Python3)

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        def getCol(up,down,index,type=0):
            data = matrix[up:down+1]
            if type == 0:
                return [x[index] for i,x in enumerate(data)]
            return [x[index] for i,x in enumerate(data) if i != 0 and i !=len(data)-1]
        #返回限定框的顺时针数据
        def getRound(left,right,up,down):
            if up == down:
                return matrix[up][left:right+1]
            if left == right:
                return getCol(up,down,left)
            return matrix[up][left:right+1] + getCol(up,down,right,1) + matrix[down][left:right+1][::-1] +getCol(up,down,left,1)[::-1]
        m = len(matrix)
        n = len(matrix[0])
        left = up = 0
        right = n - 1
        down = m - 1
        res = []
        while len(res) < m * n:
            res += getRound(left,right,up,down)
            up += 1
            down -= 1
            left += 1
            right -= 1
        return res

思路:

把矩形想象成一个箱子,沿着外壳逐层脱掉外壳,辅助变量为left,right,up,down分别表示当前箱子的左右上下边界(闭区间),然后进行遍历依次存入名为res的List中,最后返回List。

复杂度分析:

  • 时间复杂度O(nlogn) n代表的是自定义方法中使用了诸如[::-1]等切片访问操作,时间复杂度为O(n),外面的logn是因为整个外层循环的次数是对数级别的
  • 空间复杂度O(1) 额外6个变量 常数级别

运行结果:

在这里插入图片描述


本文链接: http://www.dtmao.cc/news_show_2000290.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?