力扣 88：合并两个有序数组

题目描述

给定两个按非递减顺序排列的整数数组 nums1 和 nums2，分别有长度 m、n。请将 nums2 原地 合并到 nums1，使结果仍保持非递减顺序。nums1 的总长度为 m + n，末尾的 n 个位置初始化为 0 作为缓冲区。

解题思路

与其先拼接再整体排序，不如利用“两数组已排序”这一特性，从尾部开始归并：

1. 设 p1 = m - 1、p2 = n - 1 分别指向两个数组的最后一个有效元素，tail = m + n - 1 指向合并后数组的尾部；
2. 每轮比较 nums1[p1] 和 nums2[p2]，把较大的放入 nums1[tail]，然后移动对应指针以及 tail；
3. 若 nums2 还有剩余元素（p2 >= 0），继续写入；如果只剩 nums1 元素，无需处理，因为它们已经在正确位置。

双指针从后往前填充可以避免移动大量元素，时间复杂度为 $\mathcal{O}(m+n)$，空间复杂度为 $\mathcal{O}(1)$。

代码实现

from typing import List


class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        p1 = m - 1
        p2 = n - 1
        tail = m + n - 1

        while p2 >= 0:
            if p1 >= 0 and nums1[p1] > nums2[p2]:
                nums1[tail] = nums1[p1]
                p1 -= 1
            else:
                nums1[tail] = nums2[p2]
                p2 -= 1
            tail -= 1

复杂度分析

• 时间复杂度：$\mathcal{O}(m+n)$，每个元素只移动一次；
• 空间复杂度：$\mathcal{O}(1)$，原地合并未使用额外数组。