合并两个有序的数组

题目描述给出两个已按升序排列的整数数组A和B将B合并进A使A仍为升序有序数组。数据范围0 n, m ≤ 100|A[i]| ≤ 100|B[i]| ≤ 100。注意点A预留了足够空间容纳BA的总容量为mn初始有效元素个数分别为m和n。不需要返回合并后的数组直接在A内完成合并评测会自动输出合并后的A。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的最后空位。具体做法设三个指针i m-1指向A有效部分的最后一个j n-1指向B的最后一个k mn-1指向A的最后位置空位末端循环直到B用完j 0若i 0且A[i] B[j]说明当前最大的在A[i]放到A[k]然后i--, k--否则放B[j]到A[k]然后j--, k--为什么循环条件用while (j 0)如果B已经放完了A剩下的本来就在前面且有序不用动。如果A先用完i 0那就把B剩余的全部拷到A前面即可代码里的 else 分支自然完成。publicclassSolution{publicstaticvoidmerge(int[]A,intm,int[]B,intn){intim-1,jn-1,kmn-1;while(j0){if(i0A[i]B[j])A[k--]A[i--];elseA[k--]B[j--];}}}思路二从前往后合并 双指针publicstaticvoidmerge(int[]A,intm,int[]B,intn){intj0;// B 的指针intcurLenm;// A 当前有效长度会增长for(inti0;icurLenjn;i){if(A[i]B[j]){// 把 A[i..curLen-1] 整体右移一位腾出 A[i]for(intkcurLen;ki;k--){A[k]A[k-1];}A[i]B[j];j;curLen;}}// A 扫完了但 B 还有剩直接追加到末尾while(jn){A[curLen]B[j];}}