【LeetCode每天一题】Spiral Matrix(螺旋打印数组)-蒲公英云

【LeetCode每天一题】Spiral Matrix(螺旋打印数组)

梦里梦外; 2021-12-15 14:17 290阅读 0赞

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

Example 1:

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

Example 2:

Input:
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]
思路

　　这到题的思路不难，但是在边界的处理上非常复杂。自己做了好一会也没能ac，看了以下solution写的也是听复杂度，最后看到了一个简单易懂的答案。具体思路是 我们设置一个up、down、left、right变量，来进行遍历。循环的条件就是up < down and left < right ，(and 是防止出现3*2 这种矩阵，因为下面还要继续进行殊处理) 每次循环完毕之后up, left加1， down, right减1。循环内部进行四次循环，分别添加每一层的数字。直到外层循环结束。最后在判断特殊的比如2*3这种矩阵。时间复杂度为O(m*n), 空间复杂度为O(N)（N为元素总个数）
解决代码

1 class Solution(object):
 2     def spiralOrder(self, nums):
 3         """
 4         :type matrix: List[List[int]]
 5         :rtype: List[int]
 6         """
 7         if not nums:
 8             return []
 9         
10         m , n = len(nums), len(nums[0])
11         up, down, left, right = 0, m-1, 0, n-1     # 设置上下左右变量。
12         res = []               
13         while up < down and left < right:           # 循环条件
14             for  i in range(left, right):        # 打印当前层的上半部分
15                 res.append(nums[up][i])
16             
17             for i in range(up, down):               # 打印当前层的右半部部分
18                 res.append(nums[i][right])
19             
20             for i in range( right, left,-1):        # 打印当前层的下边部分
21                 res.append(nums[down][i])
22             for i in range(down, up, -1):            # 打印当前层的左半部分
23                 res.append(nums[i][left])
24             up, down, left, right = up+1, down-1, left+1, right-1       
25         
26         if left == right:                # 如果左等于右，说明可能存在2*3 这种形式的矩阵，将最里面的一层添加
27             res.extend([nums[i][right] for i in range(up, down + 1)])
28         elif up == down:                 # 如果上等于下， 说明可能存在3*2 这种类型的矩阵。
29             res.extend([nums[up][j] for j in range(left, right + 1)])
30         return res