OJ题库：俩个有序序列（数组）合并

￡神魔★判官ぃ 2023-10-15 11:19 14阅读 0赞

**前言：**在部分大厂笔试时经常会使用[OJ][]题目，这里对《有序序列合并》进行思路分析和讲解，在这里主要使用俩种方法进行讲解，希望对各位读者有所帮助。

题目来自牛客网，欢迎各位积极挑战：[有序序列合并\_牛客题霸\_牛客网][Link 1]

--------------------

**目录**

题目相关信息：

描述

输入描述

输出描述

示例

方法一（最优解）：

设计思路

实现细节

初始化

比较逻辑

完整代码实现

方法二（暴力排序）：

--------------------

## 题目相关信息： ##

### 描述 ###

> 输入两个升序排列的序列，将两个序列合并为一个有序序列并输出。
> 
> **数据范围**：**1 ≤ n, m ≤ 1000,** 序列中的值满足 **0 ≤ val ≤ 30000**

### 输入描述 ###

> **输入包含三行：**
> 
>  *  第一行包含两个正整数 **n**, **m**，用空格分隔。**n** 表示第二行第一个升序序列中数字的个数，**m** 表示第三行第二个升序序列中数字的个数
>  *  第二行包含n个整数，用空格分隔
>  *  第三行包含m个整数，用空格分隔

### 输出描述 ###

> 输出为一行，输出长度为 **n+m** 的升序序列，即长度为 **n** 的升序序列和长度为 **m** 的升序序列中的元素重新进行升序序列排列合并

###  示例 ###

> **输入:  5 6  
>  1 3 7 9 22  
>  2 8 10 17 33 44**
> 
> **输出:  1 2 3 7 8 9 10 17 22 33 44**

--------------------

## 方法一（最优解）： ##

### 设计思路 ###

首先，确定使用数组的方式存储俩个数列，如下图所示

![6507569802314517a1dc75deaefd016c.png][]

**然后使用俩个指针分别来维护他们，每一次比较俩个指针指向的数据的大小，然后将较小的数据放在一个新的数组中，并且让指针指向下一个数据，这样反复移动指针后，我们就可以拿到从小到大的有序数据**

> ![c295b4cbcab64f2e89b9a66158472b60.png][]
> 
> ![557150211c2e4c4184f3dfe20850138f.png][]
> 
> ![caa8849c76aa46aa8cdf26ce172a0d2c.png][]

### 实现细节 ###

#### 初始化 ####

首先题目要求输入的数组的大小 **n** 和 **m** 大于 **0** 小于 **1000**，那我们就使用俩个大小为 **1000** 的数组来保存我们输入的数组，分别为**arr1** 和**arr2** ，在创建一个大小为 **1000** 的数组**arr3** 来用于输出展示，也就是记录合并后的数组

int n = 0;
        int m = 0;
    
        int arr1[1000] = { 0 };
        int arr2[1000] = { 0 };
        int arr3[1000] = { 0 };
    
        //printf("请分别输入俩个数组的大小\n");
        scanf("%d %d", &n, &m);
    
        //输入2组数据
        ///printf("请输入数组 1 的内容:\n");
        for (int i = 0; i < n; i++)
        {
            scanf("%d", &arr1[i]);
        }
        //printf("请输入数组 2 的内容:\n");
        for (int i = 0; i < m; i++)
        {
            scanf("%d", &arr2[i]);
        }

#### 比较逻辑 ####

我们使用指针**i** 来维护 **arr1**数组，使用指针**j** 来维护**arr2** 数组，使用指针**k** 来维护**arr3** 数组，让**i** 和**j** 都指向数组首元素，然后再确定俩边俩个数组都还有元素的时候，对他们指向的元素进行对比，哪边的数字小，就先将整个数字赋给**arr3** 数组，然后指针后移，再进行比较

int i = 0;//维护 arr1
        int j = 0;//维护 arr2
        int k = 0;//维护 arr3
    
        while ((i < n) && (j < m))
        {
            if (arr1[i] < arr2[j])
            {
                //printf("%d ", arr1[i++]);
                arr3[k++] = arr1[i++];
            }
            else
            {
                //printf("%d ", arr2[j++]);
                arr3[k++] = arr2[j++];
            }
        }

因为俩个数组不一定是等长的，所以当其中一个数组遍历完成后，我们要进行判断，将多余的数字之间添加在 **arr3** 的末尾，在这里因为我们的输入必须是有序的，所以可以直接添加，添加后的结果也一定是有序的

//当其中一个数组的元素排序完成后将另一个数组的剩余元素全部加在 arr3 末尾 
        if (i == n)
        {
            while (j < m)
            {
                //printf("%d ", arr2[j++]);
                arr3[k++] = arr2[j++];
            }
        }
        else
        {
            while (i < n)
            {
                //printf("%d ", arr1[i++]);
                arr3[k++] = arr1[i++];
            }
        }

#### 完整代码实现 ####

#define _CRT_SECURE_NO_WARNINGS 1
    #include<stdio.h>
    
    int main()
    {
        int n = 0;
        int m = 0;
    
        int arr1[1000] = { 0 };
        int arr2[1000] = { 0 };
        int arr3[1000] = { 0 };
    
        //printf("请分别输入俩个数组的大小\n");
        scanf("%d %d", &n, &m);
    
        //输入2组数据
        ///printf("请输入数组 1 的内容:\n");
        for (int i = 0; i < n; i++)
        {
            scanf("%d", &arr1[i]);
        }
        //printf("请输入数组 2 的内容:\n");
        for (int i = 0; i < m; i++)
        {
            scanf("%d", &arr2[i]);
        }
     
        int i = 0;//维护 arr1
        int j = 0;//维护 arr2
        int k = 0;//维护 arr3
    
        while ((i < n) && (j < m))
        {
            if (arr1[i] < arr2[j])
            {
                //printf("%d ", arr1[i++]);
                arr3[k++] = arr1[i++];
            }
            else
            {
                //printf("%d ", arr2[j++]);
                arr3[k++] = arr2[j++];
            }
        }
        //当其中一个数组的元素排序完成后将另一个数组的剩余元素全部加在 arr3 末尾 
        if (i == n)
        {
            while (j < m)
            {
                //printf("%d ", arr2[j++]);
                arr3[k++] = arr2[j++];
            }
        }
        else
        {
            while (i < n)
            {
                //printf("%d ", arr1[i++]);
                arr3[k++] = arr1[i++];
            }
        }
        for (int i = 0; i < (n + m); i++)
        {
            printf("%d ", arr3[i]);
        }
    
        return 0;
    }

## 方法二（暴力排序）： ##

这种方法效率非常的低，笔者个人建议不要使用这种方法，因为部分 OJ 题目可能会对时间复杂度或者空间复杂度进行要求，将俩个数组放在第三个数组中，然后使用冒泡排序，选择排序等等排序方法从小到大排序的方法很容易想到，在这里只需要注意使用排序的方法就可以了，这里笔者使用冒泡排序进行举例

#define _CRT_SECURE_NO_WARNINGS 1
    #include<stdio.h>
    
    int main()
    {
        int n = 0;
        int m = 0;
    
        int arr1[1000] = { 0 };
        int arr2[1000] = { 0 };
        int arr3[1000] = { 0 };
    
        printf("请分别输入俩个数组的大小\n");
        scanf("%d %d", &n, &m);
    
        //输入2组数据
        printf("请输入数组 1 的内容:\n");
        for (int i = 0; i < n; i++)
        {
            scanf("%d", &arr1[i]);
        }
        printf("请输入数组 2 的内容:\n");
        for (int i = 0; i < m; i++)
        {
            scanf("%d", &arr2[i]);
        }
    
        int i = 0;//维护 arr1
        int j = 0;//维护 arr2
        int k = 0;//维护 arr3
        //全部放入arr3
        while (i < n)
        {
            arr3[k++] = arr1[i++];
        }
        
        while (j < m)
        {
            arr3[k++] = arr2[j++];
        }
        //排序
        for (int i = 0; i < (n + m - 1); i++)
        {
            for (int k = 0; k < (n + m - i - 1); k++)
            {
                if(arr3[k] >= arr3[k+1])
                {
                    int temp = 0;
                    temp = arr3[k];
                    arr3[k] = arr3[k + 1];
                    arr3[k + 1] = temp;
                }
            }
        }
        //打印arr3
        for (int i = 0; i < (n + m); i++)
        {
            printf("%d ", arr3[i]);
        }
    
        return 0;
    }

**综上，俩个方法对于时间空间的利用效率并不相同，但都能完成我们的期望目标，但是值得注意的是，第二种方法并不能保证在部分对时间空间复杂度有要求的 OJ 题目成功运行，本次分享就到此结束了，希望我的分享对您有所帮助**

[OJ]: https://so.csdn.net/so/search?q=OJ&spm=1001.2101.3001.7020
[Link 1]: https://www.nowcoder.com/practice/a9e943b0dab142759807d0cfb6863897?tpId=107&&tqId=33381&rp=1&ru=/ta/beginner-programmers&qru=/ta/beginner-programmers/question-ranking
[6507569802314517a1dc75deaefd016c.png]: https://img-blog.csdnimg.cn/6507569802314517a1dc75deaefd016c.png
[c295b4cbcab64f2e89b9a66158472b60.png]: https://img-blog.csdnimg.cn/c295b4cbcab64f2e89b9a66158472b60.png
[557150211c2e4c4184f3dfe20850138f.png]: https://img-blog.csdnimg.cn/557150211c2e4c4184f3dfe20850138f.png
[caa8849c76aa46aa8cdf26ce172a0d2c.png]: https://img-blog.csdnimg.cn/caa8849c76aa46aa8cdf26ce172a0d2c.png