BM87　合并两个有序的数组¶

简单通过率 36.36%python3核心代码模式样例通过牛客 AC数组双指针

一句话

A 尾部留着空位，从后往前填大的，原地合并不搬家。

解题思路¶

这题考什么¶

「让写指针永远追不上读指针」这一类原地归并的构造。 A 的容量是 m + n，前 m 个是有效数据，后 n 个是预留空位。

照常规思路从前往后比较、往 A 的前部写，每写一个都要把 A 剩下的元素整体后移一格，退化成 O((m+n)^2) 次搬运。从后往前填就没有这个问题： A 的尾部本来就是空的，每次把两个序列当前的最大值放进去，写指针始终走在两个读指针的右边，不会覆盖尚未读取的数据。

三个指针都从各自的末尾起步：

i -> A 的有效末尾  m-1
j -> B 的末尾      n-1
k -> 写入位置      m+n-1

每一轮把 A[i] 与 B[j] 中较大的那个写到 A[k]，对应的读指针左移，k 左移。

走一遍 A = [4,5,6,,,_]（m=3），B = [1,2,3]（n=3）：

i j k   A[i] B[j] 取谁   A
2 2 5    6    3   A[i]   [4,5,6,_,_,6]
1 2 4    5    3   A[i]   [4,5,6,_,5,6]
0 2 3    4    3   A[i]   [4,5,6,4,5,6]

- 2 2    -    3   B[j]   [4,5,3,4,5,6]
- 1 1    -    2   B[j]   [4,2,3,4,5,6]
- 0 0    -    1   B[j]   [1,2,3,4,5,6]

安全性可以归纳证明：起始时 k = i + j + 1；每写一次 k 恰好减 1，而 i + j 至少减 1，于是恒有 k > i，写入位置永远落在未读区右边。

数据规模与复杂度¶

m, n <= 100，元素绝对值 <= 100，时限「其他语言 2 秒」。每个元素只被写一次，时间 O(m + n)、空间 O(1)，完全原地。题面明确要求不返回新数组，所以 sorted(A[:m] + B) 那类写法即便算得对，也绕开了这题唯一的考点，且复杂度是 O((m+n) log(m+n))。

坑在哪¶

真正的调用约定在签名里看不出来，本题由 driver.py 驱动：样例输入只有 [4,5,6],[1,2,3] 两段，m 与 n 并不在输入里—— 牛客后台自己取 m = len(A)、n = len(B)，并且预先把 A 扩容到 m + n 长度 （后半段是待填的空位）再调用。题解因此可以直接往 A[m .. m+n-1] 写，既不必自己 append，也不能假定 len(A) 等于 m。
返回类型是 void，答案留在入参 A 里，靠的是列表的原地可变性。写成 A = A[:m] + B 之类的重新绑定只会改动局部名字，调用方手里的列表纹丝不动，判题拿到的是未修改的原数组。
收尾只需要补 B 的剩余。i 先走完，说明 B 里剩下的都比 A 现存的元素小，必须继续往前搬；而 j 先走完时，A 剩下的元素本来就躺在 A[0..k] 的正确位置上，一个都不能再动——再写一遍会把它们复制串位。
比较用 A[i] > B[j] 走 A 分支、否则走 B 分支。相等时取哪一侧都不影响结果（值一样），但两个分支必须都写死指针移动，漏掉任何一次自减都会死循环。
m 或 n 为 0 都是合法输入：n = 0 时两个循环都不进入； m = 0 时第一个循环直接跳过，整段 B 由补漏循环搬进来。

参考实现¶

solutions/nowcoder/BM87/sol.py
from typing import List, Optional


class Solution:
    def merge(self, A: List[int], m: int, B: List[int], n: int) -> None:
        # 两个读指针指向各自的有效末尾，写指针指向扩容后 A 的最后一格
        i, j, k = m - 1, n - 1, m + n - 1
        # 从大到小往尾部填。恒有 k > i，写入位置永远在未读区右边，不会覆盖数据
        while i >= 0 and j >= 0:
            if A[i] > B[j]:
                A[k] = A[i]
                i -= 1
            else:
                A[k] = B[j]
                j -= 1
            k -= 1
        # B 还有剩：它们比 A 现存的元素都小，必须继续往前填
        while j >= 0:
            A[k] = B[j]
            j -= 1
            k -= 1
        # A 还有剩则一个都不能动：A[0..k] 上的元素已经在最终位置上了。
        # 全程原地改写入参 A，函数不返回任何东西，答案就留在 A 里

BM87 合并两个有序的数组¶