Leetcode 54.螺旋矩阵

Posted on | 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
    def spiralOrder(self, matrix):
        def spiral_coords(r1, c1, r2, c2):
            for c in range(c1, c2 + 1):
                yield r1, c
            for r in range(r1 + 1, r2 + 1):
                yield r, c2
            if r1 < r2 and c1 < c2:
                for c in range(c2 - 1, c1, -1):
                    yield r2, c
                for r in range(r2, r1, -1):
                    yield r, c1

        if not matrix: return []
        ans = []
        r1, r2 = 0, len(matrix) - 1
        c1, c2 = 0, len(matrix[0]) - 1
        while r1 <= r2 and c1 <= c2:
            for r, c in spiral_coords(r1, c1, r2, c2):
                ans.append(matrix[r][c])
            r1 += 1; r2 -= 1
            c1 += 1; c2 -= 1
        return ans
  • 时间复杂度：O(N)，N是指元素数量
  • 空间复杂度：O(N)，N是ans长度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution(object):
    def spiralOrder(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[int]
        """
        res = list()

        if not matrix:
            return res
        m,n = len(matrix),len(matrix[0])
        y1 = 0
        y2 = m-1
        x1 = 0
        x2 = n-1
        while y1<=y2 and x1<=x2:
            for i in range(x1,x2+1):
                res.append(matrix[y1][i])
            for j in range(y1+1,y2+1):
                res.append(matrix[j][x2])
            if x1<x2 and y1<y2:
                for k in range(x2-1, x1-1, -1):
                    res.append(matrix[y2][k])
                for l in range(y2-1, y1,-1):
                    res.append(matrix[l][x1])
            x1+=1
            y1+=1
            y2-=1
            x2-=1
        return res
class Solution(object):
    def spiralOrder(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[int]
        """
        if not matrix:
            return matrix
        m, n = len(matrix), len(matrix[0])
        if m == 0 or n == 0:
            return matrix
        res = []
        start = 0
        while m > start * 2 and n > start *2:
            endX = m - start - 1
            endY = n- start -1
            for i in range(start, endY+1):
                res.append(matrix[start][i])
            if start < endX:
                for i in range(start+1, endX+1):
                    res.append(matrix[i][endY])
            if start < endY and start < endX:
                for i in range(endY-1, start-1, -1):
                    res.append(matrix[endX][i])
            if start + 1 < endX and start < endY:
                for i in range(endX-1, start, -1):
                    res.append(matrix[i][start])
            start += 1
        return res