螺旋矩阵II与合并两个有序数组
- 2019 年 10 月 5 日
- 筆記
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)，最终提交如下图：
