个人主页：CSDN清风莫追

推荐一款面试、刷题神器牛客网：👉点击加入刷题大军👈

1.题目描述

描述给出一个有序的整数数组 A 和有序的整数数组 B ，请将数组 B 合并到数组 A 中，变成一个有序的升序数组

数据范围： $0\le n,m\le 100$，$|A_i|<=100$∣， $|B_i|<=100$

注意：

1. 保证 A 数组有足够的空间存放 B 数组的元素， A 和 B 中初始的元素数目分别为 m 和 n，A 的数组空间大小为 m+n

2. 不要返回合并的数组，将数组 B 的数据合并到 A 里面就好了，且后台会自动将合并后的数组 A 的内容打印出来，所以也不需要自己打印

3. A 数组在[0,m-1]的范围也是有序的

2.算法设计思路

1）归并到一个新数组 C 中

定义三个指针$a,b,c$分别指向$A,B,C$的开头，比较$a、b$指向的元素，若$A[a]<B[b]$则将$A[a]$放入$C$中，否则将$B[b]$放入$C$中，直到$A,B$中有一个数组为空，或者都为空。

然后将有剩余元素的数组中的元素转移到 C 中。

最后将 C 复制到 A 中即可。

2）将 A 复制到 C，再归并到 A 中

减少了部分的时间开销：从需要复制 m+n 个元素，到只需复制 m 个元素空间开销：C 需要的空间从 m+n 变为了 m

3）直接在 A 中操作

前面的两种思路，都是从小的元素开始归并，为了避免覆盖原来 A 中的元素，我们才需要新开一个数组 C 来中转。

但是要注意到 A 数组的尾部是空的，我们不妨先从大的元素开始归并，就可以放到 A 的末尾。

这个思路我当时也没有想到，是看了别人的题解，其中还仔细解释了为何不会导致覆盖。可以参考原文：题解 | #合并两个有序的数组#。

3.算法实现

注：这里并不是完整代码，而只是核心代码的模式

下面是思路二的代码：

class Solution {public:    void merge(int A[], int m, int B[], int n) {        int* C = new int[m];        for(int i = 0; i < m; i++){            C[i] = A[i];        }
        int a = 0, b = 0, c = 0;        while(c < m && b < n){            A[a++] = C[c] < B[b] ? C[c++] : B[b++];        }        while(c < m){            A[a++] = C[c++];        }        while(b < n){            A[a++] = B[b++];        }    }};

4.运行结果

成功通过！

结束语：

今天的分享就到这里啦，快来加入刷题大军叭！👉点击开始刷题学习👈

感谢阅读

个人主页：CSDN清风莫追