Amazon Intern：两个有序数组原地合并，为什么从尾部写？

题意与假设

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

• 训练arr1有m+n个槽，前m项有效，尾n项空余；arr2有n项，且两者不共享可被覆盖的底层存储。
• 输入升序，保留重复值；返回通过修改arr1实现，槽里的0只是占位不是特殊数据。

解题路线

1. i指向arr1最后有效值，j指向arr2最后值，k指向arr1尾槽。每次把较大候选放k并移动对应读指针，保持已写后缀为最终排序后缀。
2. 只要arr2尚有元素，k=i+j+1，所以k>i；写位置始终在未读arr1右侧，无法覆盖有效未读值。arr2读完后arr1剩余前缀已在正确位置，可以停止。
3. arr1耗尽则把arr2剩余项补到前面；arr2为空无需移动。若要稳定性，需声明相同key时的来源顺序；从尾写选second平局，可保持first在second之前。
4. 降序合同从尾写较小项，比较方向改变而容量证明不变。无序必须先排序，不能直接双指针；没有预留空间须先扩容或讨论另一种真正原地算法，避免偷加数组又称O(1)。

手动走一遍

训练例first=[1,3,7,0,0,0]、m=3、second=[2,3,6]，从后写7,6,3,3,2，最终[1,2,3,3,6,7]。first有效为空时直接填入second。

Python 参考实现

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

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

def merge_into(first, valid_count, second):
    """First has exactly valid_count+len(second) slots, ascending valid prefixes."""
    if valid_count < 0 or len(first) != valid_count+len(second) or first is second:
        raise ValueError("invalid capacity or aliased arrays")
    i,j,k = valid_count-1,len(second)-1,len(first)-1
    while j >= 0:
        if i >= 0 and first[i] > second[j]:
            first[k] = first[i]
            i -= 1
        else:
            first[k] = second[j]
            j -= 1
        k -= 1

复杂度

O(m+n)时间，O(1)额外空间，依赖容量已存在；扩容可能重新分配O(m+n)空间，需在正式API说明。

易错点与追问

容易失分的边界

• 从头写覆盖first未读元素。
• 把占位0当输入数据。
• 无预留容量仍使用该写法。

继续深挖

• 降序比较条件怎样改？
• 按record key并稳定合并怎么处理平局？
• 无序数组且不能扩容时可选什么合同？