问题：
我们有两个 已排序 的整数数组 A 和 B，其中：

• 数组 A 的末尾包含足够多的空位，数量等于数组 B 的元素个数。
• 目标是将数组 B 的所有元素合并到数组 A 中，且 A 保持 升序排列。

输入：

A = [1, 2, 3, _, _, _, _]  
B = [2, 4, 6, 100]  

输出：

A = [1, 2, 2, 3, 4, 6, 100]  

要求：
优化合并操作的时间复杂度和空间复杂度。

---

题目分析与解法思路

这是一道经典的合并问题，考查对双指针方法的灵活运用和在优化内存使用上的能力。

---

解题步骤

1. 分析与约束条件

1. 数组 A 中有足够的空位可以容纳数组 B，因此不需要额外的空间存储结果。
2. 合并操作需要在 原地 完成，即直接修改数组 A。
3. 时间复杂度需要尽可能优化。

2. 双指针逆向合并

考虑到数组 A 的末尾有空位，我们可以从 数组的末尾 开始合并，而不是从头部。逆向合并的优势在于：

• 避免覆盖数组 A 中的已有数据。
• 每次操作直接将较大的元素放入数组 A 的最后一个空位。

具体算法步骤：

1. 使用两个指针，分别指向数组 A 和数组 B 的末尾。
2. 逐个比较两个指针指向的元素，将较大的元素放到数组 A 的末尾。
3. 移动对应的指针，并继续比较，直到所有元素合并完成。

---

时间与空间复杂度分析

时间复杂度

每个元素只被访问和移动一次，因此时间复杂度为 O(m + n)，其中 m 和 n 分别为数组 A 和 B 的长度。

空间复杂度

由于是原地合并，没有使用额外的空间，因此空间复杂度为 O(1)。

---

示例解析

输入：

A = [1, 2, 3, _, _, _, _]  
B = [2, 4, 6, 100]  

过程：

1. 初始化两个指针：i = 2（A 的最后一个非空元素），j = 3（B 的最后一个元素）。同时初始化一个目标指针 k = 6（A 的最后一个位置）。
2. 比较 A[i] 和 B[j]，将较大的值放入 A[k]。
   • 第一次比较：A[i] = 3, B[j] = 100 → 将 100 放入 A[k]，更新指针：j = 2, k = 5。
   • 第二次比较：A[i] = 3, B[j] = 6 → 将 6 放入 A[k]，更新指针：j = 1, k = 4。
   • 第三次比较：A[i] = 3, B[j] = 4 → 将 4 放入 A[k]，更新指针：j = 0, k = 3。
   • 第四次比较：A[i] = 3, B[j] = 2 → 将 3 放入 A[k]，更新指针：i = 1, k = 2。
   • 第五次比较：A[i] = 2, B[j] = 2 → 将 2 放入 A[k]，更新指针：j = -1, k = 1。
3. 当 B 的所有元素都合并后，数组 A 即为最终结果。

输出：

A = [1, 2, 2, 3, 4, 6, 100]  

---

总结

本题的核心考点：

1. 对双指针法的理解和应用。
2. 时间复杂度和空间复杂度的优化能力。

通过逆向合并，我们能够以线性时间完成原地合并，符合面试中对效率和内存使用的高要求。

---

CSOAHelp 的面试辅助

在候选人回答此题时，CSOAHelp 团队提供了以下实时指导：

1. 问题拆解与思路优化： 提示使用逆向双指针法，避免从头合并导致数据覆盖。
2. 算法复杂度分析： 帮助候选人明确时间与空间效率的优化目标。
3. 示例验证与边界处理： 提供清晰的案例解析，确保解法覆盖所有边界情况。

Thanks to the rigorous preparation provided by CSOAHelp's Interview Coaching and VO Support, the candidate excelled in this challenging interview. They confidently tackled each question, earning the interviewer’s praise and securing a solid opportunity for their future career. For aspiring candidates, this demonstrates the value of structured preparation and expert guidance.

经过csoahelp的面试辅助，候选人获取了良好的面试表现。如果您需要面试辅助或面试代面服务，帮助您进入梦想中的大厂，请随时联系我。

If you need more interview support or interview proxy practice, feel free to contact us. We offer comprehensive interview support services to help you successfully land a job at your dream company.