Jianbo Dai's

mq017.螺旋矩阵

 
  • Dec 05, 2020

题目链接

啊这个题就是典型的模拟嘛，就是要处理好各种边界吧，所以我花了很多时间在试，最后终于写对了，但是空间复杂度居然比较高？不知道为什么，试试不要写成类的方法而是都写在一个函数里。这个算法的时间复杂度O（NM），空间复杂度是O（1）。

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if not matrix:
            return []

        def right(x, y, time):
            for i in range(time, col-time):
                res.append(matrix[x][i])
            if time * 2 + 1 < row:
                down(x, col - time -1, time)

        def down(x, y, time):
            for i in range(x+1, row-time):
                res.append(matrix[i][y])
            if time * 2 + 1 < col:
                left(row - time - 1, y, time)
        
        def left(x, y, time):
            for i in range(y-1, time-1, -1):
                res.append(matrix[x][i])
            if time*2 + 2 < row:
                up(x, time, time)
            
        def up(x, y, time):
            for i in range(x-1, time, -1):
                res.append(matrix[i][y])
            time += 1
            if time * 2 < col:
                right(time, y, time)

        row, col = len(matrix), len(matrix[0])
        res = []
        time = 0
        right(0, 0, time)
        return res
Search