88. 合并两个有序数组

题目

• 题号：88
• 难度：简单
• https://leetcode-cn.com/problems/merge-sorted-array/

给定两个有序整数数组nums1和nums2，将 nums2合并到nums1中，使得num1成为一个有序数组。
说明:

• 初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
• 你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。

实现

思路1 合并+排序

最容易想到的暴力解法，可以用一行python解决。

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

思路2 双指针

该题与Leetcode第21题“合并两个有序链表”很相似，所以容易想到用双指针的方法解题。
语雀内容

1. 首先定义两个指针i, j分别指向两个list的头部，然后逐一往后遍历。
2. 遍历过程中比较nums1[i]和nums2[j]的大小，将较小的值加入答案数组中，并使它的指针向后移动一位，直到某个指针遍历到结尾了。
3. 此时跳出循环后，还有一个数组没被遍历完，就直接将其剩余数字全部加到答案数组后面。

最后要额外注意该题要求在nums1上修改答案（in-place），所以需要一开始先额外定义一个数组将原本nums1中的数组进行保存。

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里的值拿出来
        copynums1 = nums1[:m]
        nums1[:] = []
        # 定义双指针
        i = 0
        j = 0
        while i<m and j<n:
            if copynums1[i] < nums2[j]:
                nums1.append(copynums1[i])
                i += 1
            else:
                nums1.append(nums2[j])
                j += 1
        # 遍历结束后至多有一个list不为空
        nums1[i+j:] = copynums1[i:] if i<m else nums2[j:]

时间复杂度：. 因为需要遍历一遍nums1和nums2两个数组。
空间复杂度：. 因为一开始定义了新数组用来保存nums1原来的值。