Spiral Matrix

川长思鸟来 2021-12-17 10:43 163阅读 0赞

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]`.

剑指offer的题目．很有意思，但是非常考验细节的题目,主体细节在circle这个函数，每次走四个方向．从左朝右，从上朝下，从右朝左，从下朝上．和剑指offer的思路不一样．我没有加过多判断．而是要求每次按行按列走都要走完，走完之后，修改index，将该行或者该列删除．复杂度Ｏ(m\*n),代码如下：

class Solution(object):
        def spiralOrder(self, matrix):
            """
            :type matrix: List[List[int]]
            :rtype: List[int]
            """
            if not matrix or not matrix[0]:
                return []
            res = []
            m = len(matrix)
            n = len(matrix[0])
            xBegin = 0
            xEnd = m - 1
            yBegin = 0
            yEnd = n - 1
            self.circle(res,matrix, xBegin, xEnd, yBegin, yEnd)
            return res
        def circle(self, res, matrix, xBegin, xEnd, yBegin, yEnd):
            if xBegin <= xEnd and  yBegin <= yEnd:
                if yBegin <= yEnd and xBegin <= xEnd: #这一行可以不需要，去掉会加速很多
                    for i in xrange(yBegin, yEnd+1):
                        res.append(matrix[xBegin][i])
                    xBegin += 1
                if xBegin <= xEnd and yBegin <= yEnd:
                    for i in xrange(xBegin, xEnd+1):
                        res.append(matrix[i][yEnd])
                    yEnd -= 1
                        
                if yBegin <= yEnd and xBegin <= xEnd:
                    for j in xrange(yEnd, yBegin-1, -1):
                        res.append(matrix[xEnd][j])
                    xEnd -= 1
                if xBegin <= xEnd and yBegin <= yEnd:
                    for j in xrange(xEnd, xBegin-1, -1):
                        res.append(matrix[j][yBegin])
                    yBegin += 1
                self.circle(res,matrix, xBegin, xEnd, yBegin, yEnd)

转载于:https://www.cnblogs.com/sherylwang/p/5813219.html