力扣面试题10.01：利用双指针法原地合并有序数组
2天前
一、题目解读
力扣面试题10.01要求将两个有序数组A和B合并成一个有序数组，且合并结果需存储在数组A中（原地修改）。需确保合并后的A元素按升序排列，同时考虑A末尾可能存在无效元素（填充0）。核心挑战在于如何在O(m+n)时间复杂度内完成合并，避免使用额外空间。
二、解题思路
采用“双指针从后向前合并”策略：
1. 初始化三个指针：i指向A的有效末尾，m-1；j指向B末尾n-1；k指向A总末尾m+n-1。
2. 从后向前比较A[i]与B[j]，将较大元素放入A[k]，同时移动对应指针。
3. 若B剩余元素未处理完，直接复制到A头部。
此思路利用A的额外空间（原无效部分）存放合并结果，避免新数组创建。
三、解题步骤
1. 初始化指针：i=m-1,j=n-1,k=m+n-1，确保遍历从末尾开始。
2. 双指针比较合并：
● 若A[i]>B[j]，将A[i]放入A[k]，i、k左移；
● 否则（含A[i]≤B[j]），将B[j]放入A[k]，j、k左移。
● 循环直至A或B遍历完毕。
3. 处理剩余元素：若B有剩余（j≥0），直接将B[j]填入A[k]，直至B为空。
4. 结果验证：此时A已有序，无需额外排序。
四、代码与注释
class Solution {
public:
void merge(vector<int>& A, int m, vector<int>& B, int n) {
// 初始化指针：i指向A末尾，m-1；j指向B末尾n-1；k指向A总末尾m+n-1
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中剩余元素已在正确位置，无需处理
}
};五、总结
双指针法巧妙利用原数组空间，实现原地合并，时间复杂度O(m+n)，空间复杂度O(1)。该解法核心在于从后向前操作，避免元素覆盖问题，适用于需高效处理的面试场景。掌握此类技巧，可显著提升算法设计与优化能力。
原创内容 转载请注明出处
