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

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
上一篇:C++之Boost Asio相关


下一篇:cpprestsdk有bug.