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

梦里梦外; 2021-12-15 14:17 236阅读 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

转载于:https://www.cnblogs.com/GoodRnne/p/10734998.html