88. 合并两个有序数组

Problem: 88. 合并两个有序数组

思路

数据范围200，太小

• 最暴力的想法：直接把nums2的有效部分覆盖掉nums1的无效部分，然后对nums1进行原地排序，时间复杂度：覆盖+排序：$O(n+nlogn)$ = $O(nlogn)$
• 优化：双指针，和归并排序一个想法，但这里由于是原地操作，所以需要先处理数值比较大的，也就是依次比较nums1和nums2两个数组元素谁大，然后放到nums1无效部分。

解题方法

双指针（这里是三个指针）
index1和index2分别指向nums1和nums2有效部分的最后
index指向nums1的最后
循环判断nums1和nums2的元素大小，较大的放到nums1的后面
更新指针
需要注意的是，同归并排序的合并过程，可能存在数组有剩余的情况，这里nums1的有效数组剩余无所谓，因为其本身就属于nums1。只需要考虑nums2，当nums2非空时，其中元素必定全部是最小的，所以直接放到nums1的最前面即可。

复杂度

时间复杂度: $O(n+m)$ 遍历两个数组

空间复杂度: $O(1)$ 指针变量

Code

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.
        """
        # 双指针
        index1, index2 = m - 1, n - 1 # 分别指向nums1和nums2有效数组的尾部
        index = n + m - 1 # 指向nums1的尾部

        # 比较两个数组的元素，谁大就放到index的位置
        while index1 >= 0 and index2 >= 0:
            if nums1[index1] <= nums2[index2]:
                nums1[index] = nums2[index2]
                index2 -= 1
            else:
                nums1[index] = nums1[index1]
                index1 -= 1
            index -= 1
        
        if index2 >= 0:
            # 如果num2有剩余 说明元素全是比nums1小的
            nums1[: index2 + 1] = nums2[: index2 + 1]