【leetcode刷题】面试经典150题 88.合并两个有序数组

leetcode刷题
面试经典150
88. 合并两个有序数组
难度：简单

文章目录

一、题目内容
二、自己实现代码
- 2.1 实现思路
- 2.2 实现代码
- 2.3 结果分析
三、官方解法
- 3.1 直接合并后排序
- - 3.1.1 算法实现
  - 3.1.2 代码实现
  - 3.1.3 代码分析
- 3.2 双指针
- - 3.2.1 算法实现
  - 3.2.2 代码实现
  - - 3.2.2.1 错误版本1
    - 3.2.2.2 错误版本2
    - 3.2.2.3 正确版本
  - 3.2.3 代码分析
- 3.3 逆指针
- - 3.3.1 算法实现
  - 3.3.2 代码实现
  - 3.1.3 代码分析
四、一些注意的地方
第三部分参考官方题解：

一、题目内容

给你两个按非递减顺序排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：
- 最终，合并后数组不应由函数返回，而是存储在数组 nums1 中
- 为了应对这种情况：
- nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，
- nums2 的长度为 n

二、自己实现代码

2.1 实现思路

可以直接将 num2覆盖到 num1的后n个元素上
借助python的sort函数，一键实现排序

2.2 实现代码

class Solution(object):
    def merge(self, nums1, m, nums2, n):
        """
        :type nums1: List[int]
        :type m: int
        :type nums2: List[int]
        :type n: int
        :rtype: None Do not return anything, modify nums1 in-place instead.
        """
        for i in range(n):
            nums1[i+m] = nums2[i]
        nums1.sort()

2.3 结果分析

在这里插入图片描述

三、官方解法

感觉直接调用sort算是取巧了，官方一定不希望这样解出来，所以，把官方解法也放过来了

3.1 直接合并后排序

3.1.1 算法实现

先将数组 nums2 放进数组 nums1 的尾部，然后直接对整个数组进行排序

3.1.2 代码实现

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        nums1[m:] = nums2
        nums1.sort()

3.1.3 代码分析

时间复杂度：O((m+n)log⁡(m+n))
排序序列长度为 m+n，套用快速排序的时间复杂度即可，平均情况为 O((m+n)log⁡(m+n))
空间复杂度：O(log⁡(m+n))
排序序列长度为 m+n，套用快速排序的空间复杂度即可，平均情况为 O(log⁡(m+n))

3.2 双指针

3.2.1 算法实现

利用num1和num2都是排好序的性质，使用双指针方法
将两个数组看作队列，每次从两个数组头部取出比较小的数字放到结果中
具体思路：
- 首先，两个初始位置都是0
- 然后，声明一下新的list，后面用来覆盖掉num1
- 开始比较第一个位置上的值，取min的放入new_list中
- 遍历结束停止

3.2.2 代码实现

3.2.2.1 错误版本1

是自己对着这个思路实现的
但是，忽略了两个list存在比较结束的情况

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        p = 0
        q = 0
        new_list = []
        while p<m or q<n:
        	if num1[p] <= num2[q]:
        		new_list.append(num1[p])
        		p += 1
			else:
				new_list.append(num2[q])
        		q += 1
		num1 = new_list

3.2.2.2 错误版本2

添加上了两个list存在比较结束的情况
对于list的覆盖，不能直接相等

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        p = 0
        q = 0
        new_list = []
        while p<m or q<n:
            if p == m:
                new_list.append(nums2[q])
                q += 1
            elif q == n:
                new_list.append(nums1[p])
                p +=1
            elif nums1[p] <= nums2[q]:
        		new_list.append(nums1[p])
        		p = p+1
            else:
				new_list.append(nums2[q])
				q += 1  
        nums1 = new_list

在这里插入图片描述

3.2.2.3 正确版本

对于list的覆盖，不能直接相等
nums1[:] = new_list

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        p = 0
        q = 0
        new_list = []
        while p<m or q<n:
            if p == m:
                new_list.append(nums2[q])
                q += 1
            elif q == n:
                new_list.append(nums1[p])
                p +=1
            elif nums1[p] <= nums2[q]:
        		new_list.append(nums1[p])
        		p = p+1
            else:
				new_list.append(nums2[q])
				q += 1  
        nums1[:] = new_list

在这里插入图片描述

3.2.3 代码分析

时间复杂度：O(m+n)
空间复杂度：O(m+n)

3.3 逆指针

3.3.1 算法实现

先将数组 nums2 放进数组 nums1 的尾部，然后直接对整个数组进行排序

3.3.2 代码实现

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        p1, p2 = m - 1, n - 1
        tail = m + n - 1
        while p1 >= 0 or p2 >= 0:
            if p1 == -1:
                nums1[tail] = nums2[p2]
                p2 -= 1
            elif p2 == -1:
                nums1[tail] = nums1[p1]
                p1 -= 1
            elif nums1[p1] > nums2[p2]:
                nums1[tail] = nums1[p1]
                p1 -= 1
            else:
                nums1[tail] = nums2[p2]
                p2 -= 1
            tail -= 1