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

Java光头强 • 2023年2月20日上午8:51 • 后端漫谈 • 阅读 228

个人主页：清风莫追
推荐一款面试、刷题神器牛客网：👉点击加入刷题大军👈

文章目录

1.题目描述
2.算法设计思路
3.算法实现
4.运行结果
结束语：

1.题目描述

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

数据范围：

≤

100

0 \le n,m \le 100

$0 \leq n, m \leq 100$ ，

∣

100

|A_i| <=100

$∣ A_{i} ∣ <= 100$ ∣，

∣

100

|B_i| <= 100

$∣ B_{i} ∣ <= 100$

注意：

保证 A 数组有足够的空间存放 B 数组的元素， A 和 B 中初始的元素数目分别为 m 和 n，A的数组空间大小为 m+n
不要返回合并的数组，将数组 B 的数据合并到 A 里面就好了，且后台会自动将合并后的数组 A 的内容打印出来，所以也不需要自己打印
A 数组在[0,m-1]的范围也是有序的

2.算法设计思路

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

定义三个指针

a,b,c

$a, b, c$ 分别指向

A,B,C

$A, B, C$ 的开头，比较

、

a、b

$a 、 b$ 指向的元素，若

[

]

[

]

A[a]<B[b]

$A [a] < B [b]$ 则将

[

]

A[a]

$A [a]$ 放入

$C$ 中，否则将

[

]

B[b]

$B [b]$ 放入

$C$ 中，直到

A,B

$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++];
        }
    }
};