Spiral Matrix

题目描述

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example, Given the following matrix:

[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

You should return [1,2,3,6,9,8,7,4,5].

解题方法

这题比较像rotate image那道题，思路不难，但是code容易出错。

• 记录下左上角和右下角的坐标位置， 不断地处理最外围一圈
• 递归的继续下一个matrix的最外围一圈

注意点

m和n有可能不相同，所以最后又可能剩下的不是一个正方形matrix,而是一行或者一列，这个需要特殊处理

Solution

class Solution(object):
    def spiralOrder(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[int]
        """
        if not matrix:
            return []

        rowNum = len(matrix)
        colNum = len(matrix[0])
        result = []
        self.helper(matrix, result, 0, 0, rowNum - 1, colNum - 1)
        return result

    def helper(self, matrix, result, startX, startY, endX, endY):
        if startX == endX:
            for i in range(startY, endY + 1):
                result.append(matrix[startX][i])
            return
        if startY == endY:
            for i in range(startX, endX + 1):
                result.append(matrix[i][startY])
            return

        # upper row
        for i in range(startY, endY):
            result.append(matrix[startX][i])

        # right column
        for i in range(startX, endX):
            result.append(matrix[i][endY])

        # bottom row
        for i in range(endY, startY, -1):
            result.append(matrix[endX][i])

        # left column
        for i in range(endX, startX, -1):
            result.append(matrix[i][startY])

        sX = startX + 1
        sY = startY + 1
        eX = endX - 1
        eY = endY - 1
        if eX >= sX and eY >= sY:
            self.helper(matrix, result, sX, sY, eX, eY)

Reference