【牛客刷题-算法】NC22 合并两个有序的数组

1.题目描述

描述

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

数据范围：

注意：

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

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

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

2.算法设计思路

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

定义三个指针a , b , c a,b,ca,b,c分别指向A , B , C A,B,CA,B,C的开头，比较a 、 b a、ba、b指向的元素，若A [ a ] < B [ b ] A[a]<B[b]A[a]<B[b]则将A [ a ] A[a]A[a]放入C CC中，否则将B [ b ] B[b]B[b]放入C CC中，直到A , B A,BA,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.运行结果

成功通过！