Jianbo Dai's

jz029.顺时针打印矩阵

 
  • Jun 02, 2020

题目链接

这个问题，再用将矩阵用图形表示出来之后更容易思考。我们可以注意到，打印矩阵的时候，我们可以将过程分解成一圈圈打印。那么有几层就有几次循环。那么如何判断矩阵里有几层圈圈呢，最关键的点在于坐上角的位置，因为这个位置不论矩阵形状如何，其坐标里的X，Y总是相等的，并且满足当循环没有终止时，该位置横坐标值的两倍小于矩阵列的数量，该位置纵坐标的

这个算法的时间复杂度是O（N），空间复杂度是O（N）。

class Solution:

    def spiralOrder1(self, matrix: List[List[int]]) -> List[int]:
        self.ans = []
        if matrix == []:
            return self.ans
        numOfRows, numOfColumns = len(matrix), len(matrix[0])
        start = 0
        while start * 2 < numOfRows and start * 2 < numOfColumns:
            self.printCircle(matrix, numOfRows, numOfColumns, start)
            start += 1
        return self.ans

    def printCircle(self, matrix, numOfRows, numOfColumns, start):
        endX, endY = numOfColumns - 1 - start, numOfRows - 1 - start
        for i in range(start, endX+1):
            self.ans.append(matrix[start][i])
        if start < endY:
            for i in range(start + 1, endY+1):
                self.ans.append(matrix[i][endX])
        if start < endX and start < endY:
            for i in range(endX - 1, start-1, -1):
                self.ans.append(matrix[endY][i])
        if start < endX and start < endY - 1:
            for i in range(endY - 1, start, -1):
                self.ans.append(matrix[i][start])

    def spiralOrder2(self, matrix: List[List[int]]) -> List[int]:
        res = []
        while matrix:
            res += matrix.pop(0)
            matrix = list(zip(*matrix))[::-1]
        return res
Search