力扣10.01题详解：从后向前合并两个有序数组
一、问题理解
数组A有足够的空间容纳A和B的所有元素
A的有效元素数量为m
B的有效元素数量为n
合并后A应该保持有序
二、解法分析
常见的合并有序数组方法有三种：
直接合并后排序：
将B复制到A的末尾，然后整体排序
时间复杂度O((m+n)log(m+n))，不够高效
新建数组合并：
创建新数组，按顺序从A和B取元素
时间复杂度O(m+n)，但需要额外空间
从后向前合并（最优解法）：
利用A末尾的空闲空间
从两个数组的末尾开始比较
时间复杂度O(m+n)，空间复杂度O(1)
三、最优解法详解
我们采用第三种方法，具体步骤如下：
初始化指针：
i指向A的最后一个有效元素(m-1)
j指向B的最后一个元素(n-1)
k指向A的最后一个位置(m+n-1)
比较合并：
比较A[i]和B[j]
将较大的元素放入A[k]
相应指针前移
处理剩余元素：
如果B还有剩余元素，全部复制到A中
A的剩余元素已经在正确位置，无需处理
四、代码细节分析
指针初始化：
int i = m - 1, j = n - 1, k = m + n - 1;
这三个指针分别指向A、B的末尾和合并后的末尾
主循环：
while (i >= 0 && j >= 0) { if (A[i] > B[j]) { A[k--] = A[i--]; } else { A[k--] = B[j--]; } }比较并放入较大的元素，直到其中一个数组遍历完
剩余元素处理：
while (j >= 0) { A[k--] = B[j--]; }只需要处理B的剩余元素，因为A的剩余元素已经在正确位置
五、边界情况考虑
A为空：直接复制B到A
B为空：A保持不变
m=0或n=0：特殊处理
所有元素相同：不影响算法正确性
六、完整代码
class Solution {
public:
void merge(vector<int>& A, int m, vector<int>& B, int n) {
// 初始化三个指针：
// i指向A的最后一个有效元素
// j指向B的最后一个元素
// k指向A的最后一个位置
int i = m - 1, j = n - 1, k = m + n - 1;
// 从后向前遍历，比较并合并
while (i >= 0 && j >= 0) {
if (A[i] > B[j]) {
A[k--] = A[i--]; // A的元素较大，放入末尾
} else {
A[k--] = B[j--]; // B的元素较大或相等，放入末尾
}
}
// 如果B中还有剩余元素，全部复制到A中
while (j >= 0) {
A[k--] = B[j--];
}
// A中剩余元素已经在正确位置，无需处理
}
};原创内容 转载请注明出处
