LeetCode.88 合并两个有序数列（python解法）

题目

给定两个有序整数数组 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]

solution_1

思路：创建一个长度为 $m+n$的新序列，把第一个序列的前 $m$个和第二个序列的前 $n$个放入新序列，对新序列排序后放入第一个序列。

结果：执行用时：44 ms
排名：战胜96.96%

代码如下

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 it-place instead.
        """
        nums = list(range(m+n))  # 新序列
        for i in range(m):  # 第一个序列的前m个放入新序列
            nums[i]=nums1[i]
        for j in range(n):  # 第二个序列的前n个放入新序列
            nums[m+j]=nums2[j]
        nums.sort()  # 新序列排序
        for i in range(m+n):
            nums1[i]=nums[i]

solution_2

思路：双指针，第一个指针从第一个序列的最大值从后往前扫描，第二个指针从第二个序列的最大值从后往前扫描，每次比较两个指针的值，把较大的依次从第一个序列的 $m+n-1$位置往前放置。

结果：执行用时：52 ms
排名：战胜83.70%

代码如下

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 it-place instead.
        """
        i = m - 1  # 第一个指针
        j = n - 1  # 第二个指针
        while j >= 0:
            if (i == -1)or(nums1[i]<=nums2[j]):  # 第一个指针走到头之后，直接把第二个序列往第一个序列中放就可以了
                nums1[i+j+1]=nums2[j]
                j -= 1
            else:
                nums1[i+j+1]=nums1[i]
                i -= 1

参考资料：

合并两个有序数组

转载：https://blog.csdn.net/weixin_41638083/article/details/101542185