合并两个有序数组

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

• 最终合并后的数组不应由函数返回，而是存储在 nums1 中。
• nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0，应忽略。
• nums2 的长度为 n。

示例

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3  
输出：[1,2,2,3,5,6]  

解题思路

1. 为什么不能直接合并后排序？

如果直接将 nums2 拼接到 nums1 的末尾再排序，时间复杂度为 O((m+n)log(m+n))，但利用两个数组已排序的特性，可以优化到 O(m+n)。

2. 核心思路：双指针从后往前合并

• 由于 nums1 后半部分是空闲的（填充 0），如果从前往后合并，会覆盖未比较的元素。
• 改为从后往前合并：比较 nums1 和 nums2 的当前最大值，将较大者放到 nums1 的末尾。
• 这样无需额外空间（原地修改），且不会覆盖未处理的元素。

详细步骤

1. 初始化三个指针

   • p1：指向 nums1 的最后一个有效元素（索引 m-1）。
   • p2：指向 nums2 的最后一个元素（索引 n-1）。
   • p：指向 nums1 的最后一个位置（索引 m+n-1），用于放置当前最大值。

2. 循环比较并填充

   • 当 p1 >= 0 且 p2 >= 0 时，比较 nums1[p1] 和 nums2[p2]：
     • 如果 nums1[p1] > nums2[p2]，将 nums1[p1] 放到 nums1[p]，然后 p1-- 和 p--。
     • 否则，将 nums2[p2] 放到 nums1[p]，然后 p2-- 和 p--。

3. 处理剩余元素

   • 如果 nums2 还有剩余元素（p2 >= 0），说明这些元素比 nums1 剩余的都小，直接复制到 nums1 前端。
   • 如果 nums1 有剩余元素，则它们已经在正确位置，无需操作。

举例演示（以示例为例）

初始状态：

nums1 = [1, 2, 3, 0, 0, 0], m=3  
nums2 = [2, 5, 6], n=3  
p1=2, p2=2, p=5

步骤 1：比较 nums1[2]=3 和 nums2[2]=6，6 更大，放 nums1[5]=6，p2=1, p=4

nums1 = [1, 2, 3, 0, 0, 6]

步骤 2：比较 3 和 5，5 更大，放 nums1[4]=5，p2=0, p=3

nums1 = [1, 2, 3, 0, 5, 6]

步骤 3：比较 3 和 2，3 更大，放 nums1[3]=3，p1=1, p=2

nums1 = [1, 2, 3, 3, 5, 6]

步骤 4：比较 nums1[1]=2 和 nums2[0]=2，相等，放 nums1[2]=2，p2=-1, p=1

nums1 = [1, 2, 2, 3, 5, 6]

此时 p2=-1，循环结束，nums2 已全部合并完成。最终结果即为 [1,2,2,3,5,6]。

代码实现（Python）

def merge(nums1, m, nums2, n):
    p1, p2, p = m-1, n-1, m+n-1
    while p1 >= 0 and p2 >= 0:
        if nums1[p1] > nums2[p2]:
            nums1[p] = nums1[p1]
            p1 -= 1
        else:
            nums1[p] = nums2[p2]
            p2 -= 1
        p -= 1
    # 如果 nums2 还有剩余
    if p2 >= 0:
        nums1[:p2+1] = nums2[:p2+1]

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