从逆向双指针到完美合并：剖析两个有序数组合并的经典解法

一、问题场景与挑战

1.1 问题描述

给定两个按非递减顺序排列的整数数组 nums1 和 nums2，要求将 nums2 合并到 nums1 中，并保证合并后的数组仍然有序。其中：

• nums1 的初始有效长度为 m，总长度为 m+n
• nums2 的长度为 n

1.2 隐藏陷阱

当我们尝试直接从头开始合并时，会遇到一个致命问题：可能覆盖 nums1 中尚未处理的元素。例如：

nums1 = [4,5,6,0,0,0]  # m=3
nums2 = [1,2,3]         # n=3

若从左向右合并，当处理第一个元素时就会覆盖 nums1[0] 的原始值 4，导致后续操作出错。

二、算法设计的思维演进

2.1 初始思路：暴力合并后排序

• 步骤：
  1. 将 nums2 直接拷贝到 nums1 的尾部
  2. 调用排序算法
• 缺陷：
  • 时间复杂度：O((m+n)log(m+n))
  • 浪费了输入数组原本有序的特性

2.2 改进思路：正向双指针

• 实现方式：
  • 使用额外空间存储中间结果
  • 比较两个数组的头部元素
• 问题：
  • 空间复杂度 O(m+n)
  • 需要额外的拷贝操作

2.3 终极方案：逆向双指针

• 灵感来源：
  • 发现 nums1 尾部有预留空间
  • 利用数组已排序的特性，从最大值开始填充
• 优势：
  • 时间复杂度 O(m+n)
  • 空间复杂度 O(1)
  • 完全利用现有空间

三、关键代码深度解析

3.1 代码实现

void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    int pos = m-- + n-- - 1;
    while (m >= 0 && n >= 0) {
        nums1[pos--] = nums1[m] > nums2[n] ? nums1[m--] : nums2[n--];
    }
    while (n >= 0) {
        nums1[pos--] = nums2[n--];
    }
}

3.2 灵魂代码剖析

（1）索引初始化魔法

int pos = m-- + n-- - 1;

• 数值计算：

  • pos 初始值 = (m + n - 1)
  • 例如当 m=3，n=3 时，pos=5（对应索引 0-5 的第六个位置）

• 副作用操作：

  • m-- 使 m 变为 2（指向 nums1 最后一个有效元素）
  • n-- 使 n 变为 2（指向 nums2 最后一个有效元素）

• 错误示范：

  // 错误写法：会导致后续访问越界
  int pos = m + n - 1;
  

  此时 m 和 n 未递减，当访问 nums1[m] 时将越界访问（例如 m=3 时访问索引3，但有效索引为0-2）

（2）元素选择策略

nums1[pos--] = nums1[m] > nums2[n] ? nums1[m--] : nums2[n--];

• 决策逻辑：

  • 总是选择当前最大的元素
  • 优先消耗 nums1 的元素（因为最终结果存放在 nums1 中）

• 操作顺序：

  1. 比较 nums1[m] 和 nums2[n]
  2. 将较大值放入 pos 位置
  3. 移动对应数组的指针和 pos 指针

（3）剩余元素处理

while (n >= 0) {
    nums1[pos--] = nums2[n--];
}

• 为什么不需要处理 nums1 的剩余元素？
  • nums1 的剩余元素已经位于正确的位置
  • 例如：当 nums1 = [7,8,9,0,0,0]，nums2 = [1,2,3] 时，nums1 的前三个元素无需移动

四、算法正确性验证

4.1 案例推演

输入：

nums1 = [1,2,3,0,0,0], m=3
nums2 = [2,5,6], n=3

执行过程：

步骤	m	n	pos	nums1	操作说明
初始化	2	2	5	[1,2,3,0,0,0]	比较3 vs 6
1	2	1	4	[1,2,3,0,0,6]	放入6，n减1
2	2	0	3	[1,2,3,0,5,6]	比较3 vs 5
3	2	-1	2	[1,2,3,3,5,6]	比较3 vs 2
4	1	-1	1	[1,2,2,3,5,6]	处理剩余元素完成

4.2 边界测试

测试案例1：

nums1 = [0], m=0, nums2=[1], n=1

• 直接执行第二个 while 循环，将 1 放入 pos=0 的位置

测试案例2：

nums1 = [2,0], m=1, nums2=[1], n=1

• 比较 2 和 1 → 放入2
• 处理剩余元素放入1

五、工程实践中的启示

5.1 设计原则

1. 空间利用优先：充分利用现有内存空间
2. 副作用控制：警惕自增/自减操作的顺序
3. 防御性编程：明确索引的合法范围

5.2 调试技巧

• 索引追踪：在关键步骤打印 m、n、pos 的值
• 边界测试：专门测试 m=0 或 n=0 的情况
• 内存监控：使用 AddressSanitizer 检查越界访问

六、复杂度分析

指标	性能
时间复杂度	O(m+n)
空间复杂度	O(1)
最佳情况	O(min(m,n))
最差情况	O(m+n)

七、拓展思考

1. 如果要求稳定排序怎么办？

   • 需要优先保留 nums1 元素的原始顺序
   • 需修改比较逻辑，处理相等元素的顺序

2. 如何处理 K 个有序数组合并？

   • 使用最小堆维护 K 个指针
   • 时间复杂度 O(NlogK)，N 为总元素数

3. 当内存极度受限时：

   • 使用插入排序思想，时间复杂度 O(mn)
   • 但需权衡时间与空间成本

这个经典的数组操作问题，展现了逆向思维在算法设计中的强大威力。通过深入理解指针操作和索引控制，我们不仅解决了特定问题，更培养了对内存布局和操作顺序的敏感度，（推荐阅读：《深入理解计算机系统》）这对处理各种系统级编程问题都具有重要价值。