一. 题目
1. 题目
描述输入两个升序排列的序列，将两个序列合并为一个有序序列并输出。 数据范围：
,
， 序列中的值满足
输入描述： 输入包含三行， 第一行包含两个正整数n, m，用空格分隔。n表示第二行第一个升序序列中数字的个数，m表示第三行第二个升序序列中数字的个数。 第二行包含n个整数，用空格分隔。 第三行包含m个整数，用空格分隔。 输出描述： 输出为一行，输出长度为n m的升序序列，即长度为n的升序序列和长度为m的升序序列中的元素重新进行升序序列排列合并。 示例1 输入： 5 6 1 3 7 9 22 2 8 10 17 33 44 输出： 1 2 3 7 8 9 10 17 22 33 44
原题链接
牛客网_BC100_有序序列合并
二. 解题思路
1. 思路分析
(1)对于两个升序排列的数组，合并为一个升序排列的数组。可以直接把两个数组放到一个数组中，在对合并之后的数组排序即可，但是时间复杂度高。
(2)采用如下方法：分别用下标i与j记录数组arr1与arr2的元素，用下标k记录数组arr3的元素。
(3)在i<n同时j<m条件下，比较arr[i]与arr[j]的大小，小的一方存入数组arr3中，之后相应的下标增加1然后继续比较直到条件不成立。
(4)接下来有三种情况：当两个数组长度相同时，合并行为结束。
(5)当i<n且j=m时，把余下的数组arr1中的元素存入到数组arr3中。
(6)当j<m且i=n时，把余下的数组arr2中的元素存入到数组arr3中。
(7)输出数组arr3中的值。
2. 代码详解
代码语言：javascript复制#include <stdio.h>
#include <stdlib.h>
int main(){
int n,m;
scanf("%d %d", &n, &m);
int* p1 = (int*)malloc(sizeof(int)*n);
int* p2 = (int*)malloc(sizeof(int)*m);
int* p3 = (int*)malloc(sizeof(int)*(n m));
int i = 0;
for(i=0; i<n; i ){
scanf("%d", &p1[i]);
}
for(i=0; i<m; i ){
scanf("%d", &p2[i]);
}
i=0;
int j = 0;
int k = 0;
while(i<n && j<m){
if(p1[i] < p2[j]){
p3[k ] = p1[i ];
}
else{
p3[k ] = p2[j ];
}
}
while(i==n && j<m){
p3[k ] = p2[j ];
}
while(i<n && j==m){
p3[k ] = p1[i ];
}
for(i=0; i<n m; i ){
printf("%d ", p3[i]);
}
free(p1);
free(p2);
free(p3);
return 0;
}三. 本题知识与收获
题目给出的很特殊的升序排列的数组。为数组开辟内存空间时可以使用变长数组但是注意不要初始化。也可以使用动态内存分配。
