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

ftggdnt

一、题目解读

力扣面试题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与B[j]，将较大元素放入A[k]，同时移动对应指针。

3. 若B剩余元素未处理完，直接**到A头部。

此思路利用A的额外空间（原无效部分）存放合并结果，避免新数组创建。

三、解题步骤

1. 初始化指针：i=m-1,j=n-1,k=m+n-1，确保遍历从末尾开始。

2. 双指针比较合并：

● 若A>B[j]，将A放入A[k]，i、k左移；

● 否则（含A≤B[j]），将B[j]放入A[k]，j、k左移。

● 循环直至A或B遍历完毕。

3. 处理剩余元素：若B有剩余（j≥0），直接将B[j]填入A[k]，直至B为空。

4. 结果验证：此时A已有序，无需额外排序。

四、代码与注释

1. class Solution {  
   
2. public:  
   
3.     void merge(vector<int>& A, int m, vector<int>& B, int n) {  
   
4.         // 初始化指针：i指向A末尾，m-1；j指向B末尾n-1；k指向A总末尾m+n-1  
   
5.         int i = m - 1, j = n - 1, k = m + n - 1;  
   
6.         
   
7.         // 从后向前遍历，比较并合并  
   
8.         while (i >= 0 && j >= 0) {  
   
9.             if (A[i] > B[j]) {  
   
10.                 A[k--] = A[i--];  // A的元素较大，放入末尾  
    
11.             } else {  
    
12.                 A[k--] = B[j--];  // B的元素较大或相等，放入末尾  
    
13.             }  
    
14.         }  
    
15.         
    
16.         // 若B中还有剩余元素，全部**到A中  
    
17.         while (j >= 0) {  
    
18.             A[k--] = B[j--];  
    
19.         }  
    
20.         
    
21.         // A中剩余元素已在正确位置，无需处理  
    
22.     }  
    
23. };

复制代码

五、总结

双指针法巧妙利用原数组空间，实现原地合并，时间复杂度O(m+n)，空间复杂度O(1)。该解法核心在于从后向前操作，避免元素覆盖问题，适用于需高效处理的面试场景。掌握此类技巧，可显著提升算法设计与优化能力。

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