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