螺旋矩阵你听过？
螺旋矩阵你听过？
公众号guangcity
发布于 2019-09-20 11:36:48
发布于 2019-09-20 11:36:48
leetcode爬登之旅(18)
【今日知图】
屏幕移动
ctrl+b 向上翻页
ctrl+f 向下翻页
H Head 屏幕顶部
M Middle 屏幕中间
L Low 屏幕底部
0.说在前面1.螺旋矩阵2.作者的话
0.说在前面
昨天满课，我还是坚持来刷题了，写文时间是晚上10点45，刷题时间是10点，今日题目leetcode上的螺旋矩阵，这道题思路简单，实现困难，，对于考研的同学建议仔细看看，因为我们考研复试考了的。。。
算法分析及算法实现及算法思路是很重要的，每周两篇算法三部曲，你们坚持下来了？我现在坚持到第18篇了，哈哈，一起坚持下去！
下面一起来分析！
1.螺旋矩阵
题目
给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。
示例 1:
输入:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]
示例 2:
输入:
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]
]
输出: [1,2,3,4,8,12,11,10,9,5,6,7]
思路
先从左往右移动，再从上到下移动，再从右向左移动，再从下到上移动。
分为以上四部分，也就是代码需要实现上述四个流程即可~~
最后发现自己写的代码太烂了，然后学习了一下网上的风格~，修改后如下面实现部分~
实现
class Solution:
def spiralOrder(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[int]
"""
if not matrix:
return []
# 最终结果
output_list = []
# 行index
down = len(matrix) - 1
# 列index
right = len(matrix[0]) - 1
left = 0 # 左边
up = 0 # 上边
while left <= right and up <= down:
# 左到右
i = left
while True:
if i > right:
break
output_list.append(matrix[up][i])
i += 1
# 行下移
up += 1
# 上到下
j = up
while True:
if j > down:
break
output_list.append(matrix[j][right])
j += 1
# 列左移
right -= 1
# 右到左
p = right
if (up <= down):
while True:
if p < left:
break
# print(matrix[down][p])
output_list.append(matrix[down][p])
p -= 1
# print("----------")
# 行上移
down -= 1
# 下到上
q = down
if (left <= right):
while True:
if q < up:
break
output_list.append(matrix[q][left])
q -= 1
left += 1
return output_list
分析
时间复杂度：O(n^2)，空间复杂度：O(n)
击败人数：82.62%，耗时44ms
学习文章 https://blog.csdn.net/acttell/article/details/80789299
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2018-11-13，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录