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

思路

• 题目中有三个关键信息：两个数组均已排序→ 合并有序数组的典型解法是双指针，可以在线性时间内完成。
• 要求结果仍然有序，且必须原地修改 nums1→ 不能新建数组，且需要避免覆盖 nums1 中尚未处理的元素。
• nums1 末尾预留了足够空间→ 说明可以从数组末尾开始填充，采用从后向前的双指针策略。
  基于以上信息，使用三个指针分别指向：nums1 的有效末尾nums2 的末尾合并后数组的末尾

解题过程

• 初始化指针 i = m - 1，j = n - 1，k = m + n - 1。
• 当两个数组均未遍历完时：比较 nums1[i] 和 nums2[j]将较大的元素放入 nums1[k]移动对应指针循环结束后，若 nums2 仍有剩余元素，依次复制到 nums1 前部即可。

复杂度

• 时间复杂度：O(m + n)每个元素最多被处理一次。
• 空间复杂度：O(1)只使用常数个指针，原地完成合并。

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        i_1 = m - 1
        i_2 = n - 1
        k = m + n - 1

        # If nums1 has no valid elements
        if m == 0:
            nums1[:n] = nums2
            return

        while i_1 >= 0 and i_2 >= 0:
            if nums1[i_1] > nums2[i_2]:
                nums1[k] = nums1[i_1]
                i_1 -= 1
            else:
                nums1[k] = nums2[i_2]
                i_2 -= 1
            k -= 1

        # Copy remaining nums2 elements if any
        while i_2 >= 0:
            nums1[k] = nums2[i_2]
            i_2 -= 1
            k -= 1

举一反三

1. 合并两个有序数组（返回新数组）变化点：不要求原地修改，可以新建数组。训练重点：双指针从前向后对比“原地合并”和“新数组合并”的差异
2. 合并两个有序链表（LeetCode 21）变化点：数组变为链表，不能随机访问。训练重点：双指针思想在不同数据结构中的应用指针移动逻辑而非下标操作
3. 删除有序数组中的重复项（LeetCode 26）变化点：不是合并两个数组，而是在一个有序数组中压缩数据。训练重点：快慢指针如何利用有序性减少比较次数
4. 删除有序数组中的重复项 II（LeetCode 80）变化点：每个元素最多保留两次。训练重点：指针含义设计利用“已处理区间”的性质
5. 有序数组的交集（LeetCode 350）变化点：不再是简单合并，而是找公共部分。训练重点：指针同步移动的条件判断相等 / 不等时的处理策略
6. 合并区间（LeetCode 56）变化点：元素变为区间，但仍依赖排序。训练重点：“先排序 + 一次扫描”从“有序数组”抽象到“有序结构”
7. 合并 K 个有序数组 / 链表（LeetCode 23）变化点：从 2 个变成 K 个。训练重点：分治思想或使用最小堆优化复杂度
8. 在有序数组中原地插入一个元素变化点：不是整体合并，只插入一个数。训练重点：从后向前移动元素与本题“从后填充”的思想完全一致

作者：A2pvNKAqBW
链接：https://leetcode.cn/problems/merge-sorted-array/solutions/3857220/he-bing-liang-ge-you-xu-shu-zu-python-ji-mi3z/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。