Meta 合并两排序数组：从尾写入与容量合同

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• first长度m+n，前m项排序、后n项仅容量；second前n项排序且与first不是同一对象。修改first、second不变。
• 重复值保留，训练从尾遇等值优先second，使first原等值保留在前；不扩展first。

解题路线

1. i=m−1、j=n−1、write=m+n−1，比较两侧最大未处理值写到尾，再移动对应指针。这样写入位置始终不会覆盖first未读前缀。
2. 只需循环到j<0，若second耗尽，剩余first已在正确位置；若first耗尽则把second前缀继续填完。
3. 从前写会用新小值覆盖first后续未读元素，除非额外缓存/搬移。尾部预留空间正是本题O(1)辅助的前提。
4. 容量/有效长度校验与两个对象alias检查在入口做；排序前提由题面保证，如果函数要验证，还需扫描成本。

手动走一遍

first=[1,3,5,_,_,_]、second=[2,4,6]，先写6/5/4/3/2/1，结果[1,2,3,4,5,6]。m0直接复制second；n0first不变。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def merge_into(first,m,second,n):
    """first length m+n with tail capacity, sorted valid prefixes; lists distinct.

    Mutates first; second unchanged. Equal values choose second when filling back.
    """
    if first is second or not 0<=m<=len(first) or not 0<=n<=len(second) or len(first)!=m+n:
        raise ValueError('invalid capacity or alias')
    i=m-1;j=n-1;write=m+n-1
    while j>=0:
        if i>=0 and first[i]>second[j]:first[write]=first[i];i-=1
        else:first[write]=second[j];j-=1
        write-=1
    return first

复杂度

O(m+n)时间/O(1)算法辅助空间，使用已有尾容量；first输出空间本来存在，不把输入复制后仍称原地。

易错点与追问

容易失分的边界

• 把尾占位符也当排序数据。
• 前向写入覆盖未读first元素。

继续深挖

• 如果两数组都没有尾空间，如何用O(m+n)新输出归并？
• k路归并为什么需要heap或分治，当前两指针不能直接照搬？