合并两个有序的数组

题目

• 描述：给出两个已按升序排列的整数数组A和B，将B合并进A，使A仍为升序有序数组。
• 数据范围：0 < n, m ≤ 100，|A[i]| ≤ 100，|B[i]| ≤ 100。
• 注意点：
  1. A预留了足够空间容纳B（A的总容量为m+n），初始有效元素个数分别为m和n。
  2. 不需要返回合并后的数组，直接在A内完成合并；评测会自动输出合并后的A。
  3. A[0..m-1]本身是有序的。
• 示例：
  • 输入：[4,5,6],[1,2,3]→ 输出：[1,2,3,4,5,6]
  • 输入：[1,2,3],[2,5,6]→ 输出：[1,2,2,3,5,6]

https://www.nowcoder.com/questionTerminal/89865d4375634fc484f3a24b7fe65665

思路一：从后往前合并 + 双指针⭐

用“从后往前合并”的思路（双指针）：

• 已知A的前m个元素有序，B的前n个元素有序，且A末尾有n个空位可用。
• 如果从前往后插入，遇到要插入的元素就得把A后面的元素整体右移，代价高且容易覆盖数据。
• 所以反过来：从两个数组的“尾部”开始比较，把更大的那个放到A的最后空位。

具体做法：

1. 设三个指针

   • i = m-1指向A有效部分的最后一个
   • j = n-1指向B的最后一个
   • k = m+n-1指向A的最后位置（空位末端）

2. 循环直到B用完（j < 0）

   • 若i >= 0且A[i] > B[j]：说明当前最大的在A[i]，放到A[k]，然后i--, k--
   • 否则：放B[j]到A[k]，然后j--, k--

3. 为什么循环条件用while (j >= 0)

   • 如果B已经放完了，A剩下的本来就在前面且有序，不用动。
   • 如果A先用完（i < 0），那就把B剩余的全部拷到A前面即可（代码里的 else 分支自然完成）。

publicclassSolution{publicstaticvoidmerge(int[]A,intm,int[]B,intn){inti=m-1,j=n-1,k=m+n-1;while(j>=0){if(i>=0&&A[i]>B[j])A[k--]=A[i--];elseA[k--]=B[j--];}}}

思路二：从前往后合并 + 双指针

publicstaticvoidmerge(int[]A,intm,int[]B,intn){intj=0;// B 的指针intcurLen=m;// A 当前有效长度（会增长）for(inti=0;i<curLen&&j<n;i++){if(A[i]>B[j]){// 把 A[i..curLen-1] 整体右移一位，腾出 A[i]for(intk=curLen;k>i;k--){A[k]=A[k-1];}A[i]=B[j];j++;curLen++;}}// A 扫完了但 B 还有剩：直接追加到末尾while(j<n){A[curLen++]=B[j++];}}