螺旋矩阵II与合并两个有序数组
螺旋矩阵II与合并两个有序数组
公众号guangcity
发布于 2019-09-20 11:39:51
发布于 2019-09-20 11:39:51
leetcode攀登之旅(19)
【今日知图】
选中文本(可视模式)
v 可视模式 从光标位置开始按照正常模式选择文本
V 可视行模式 选中光标经过的完整行
ctrl+v 可视块模式 垂直方向选中文本
ggvG 选中所有内容
0.说在前面1.螺旋矩阵II2.合并两个有序数组3.作者的话
0.说在前面
昨天周五，没能按时发leetcode，说声抱歉，今天补上，每周的两次刷算法，必不可少，今日刷题两篇，分别是螺旋矩阵II与合并两个有序数组！
1.螺旋矩阵II
问题
给定一个正整数 n，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。
示例:
输入: 3
输出:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]
思路
跟前面的螺旋矩阵I思路一样，唯一变动的是将数据添加到list当中，这里改为设置一个数，而这个数就是计数器，前面new一个二维数组即可！
实现
class Solution:
def generateMatrix(self, n):
# 最终结果
output_list = [([0] * n) for i in range(n)]
# 行index
down = n-1
# 列index
right = n-1
left = 0 # 左边
up = 0 # 上边
value = 1
while left <= right and up <= down:
# 左到右
i = left
while True:
if i > right:
break
output_list[up][i]=value
i += 1
value+=1
# 行下移
up += 1
# 上到下
j = up
while True:
if j > down:
break
output_list[j][right] = value
j += 1
value+=1
# 列左移
right -= 1
# 右到左
p = right
if (up <= down):
while True:
if p < left:
break
# print(matrix[down][p])
output_list[down][p] = value
p -= 1
value+=1
# print("----------")
# 行上移
down -= 1
# 下到上
q = down
if (left <= right):
while True:
if q < up:
break
# print(matrix[q][left])
output_list[q][left] = value
q -= 1
value+=1
left += 1
return output_list
分析
时间复杂度O(n^2)，空间复杂度O(n^2)，已经是最优结果，最终提交如下图：
2.合并两个有序数组
问题
给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。
说明:
- 初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
- 你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
示例:
输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
输出: [1,2,2,3,5,6]
思路
这里提供两种思路，思路一：由于这里直接给定了数组有效长度，所以这道题便的十分简单，直接将数组2的所有有效数据添加到数组1中无效数据开头到结尾即可，直接使用切片完成！
思路二：由于题中说了，nums1数组大于num2数组，那么我们将两个数据有效部分m+n合并，就是最终的有效数据总量，然后从后往前遍历，如果最后的nums2还有数据，那么直接循环添加到前面即可！这里直接做的操作是，原地修改nums1！
重点！！！记住这个函数无返回值！！！
实现一
class Solution:
def merge(self, nums1, m, nums2, n):
nums1[m:] = nums2[:n]
nums1.sort()
分析
时间复杂度O(n)，空间复杂度O(1)，最终提交如下图：
实现二
class Solution:
def merge(self, nums1, m, nums2, n):
high = m+n-1
m=m-1
n=n-1
while m>=0 and n>=0:
if nums1[m]>nums2[n]:
nums1[high] = nums1[m]
high-=1
m-=1
else:
nums1[high] = nums2[n]
high -= 1
n -= 1
while n>=0:
nums1[high] = nums2[n]
high -= 1
n -= 1
# 下面一行注释掉，看题！！！没有返回值！！！
#return nums1
分析
时间复杂度O(n)，空间复杂度O(1)，最终提交如下图：
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2018-11-17，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录