力扣面试题10.01：利用双指针法原地合并有序数组

一、题目解读

力扣面试题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)。该解法核心在于从后向前操作，避免元素覆盖问题，适用于需高效处理的面试场景。掌握此类技巧，可显著提升算法设计与优化能力。