Question

用c或c++题目描述:给你两个有序的数组.合并这两个数组成为一个新的有序数组,并输出.

题目描述：
给你两个有序的数组。合并这两个数组成为一个新的有序数组，并输出。

输入格式：
第一行输入两个整数n,m 第二行输入n个数，表示第一个有序数组 第三行输入m个数，表示第二个有序数组

输出格式：
输出n+m个数,表示两个数组合并之后的结果。

样例输入：
3 4
4 5 8
1 3 6 7

样例输出：
1 3 4 5 6 7 8

约定：
1<=n<=5000000,1<=m<=5000000,所有的数都在有符号32位整数范围内

提示：
注意数据范围

Answer 1

#include <iostream>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    
    int i, j, index, n, m;
    cin >> n >> m;
    
    int *a = new int[n];
    int *b = new int[m];
    int *c = new int[n+m];
    
    for(i = 0; i < n; i++)
        cin >> a[i];
    for(j = 0; j < m; j++)
        cin >> b[j];
    
    for(i=0, j=0, index=0; i<n&&j<m; )
        c[index++] = a[i]<b[j] ? a[i++]:b[j++];
    
    if(i == n)
        while(j < m)
            c[index++] = b[j++];
    else
        while(i < n)
            c[index++] = a[i++];
            
    cout << c[0];        
    for(index = 1; index <n+m; ++index)
        cout <<  " " << c[index];                            
    
    return 0;
}

追问

我提交了，是超时，样例对了，有改进的吗？

Answer 2

#include<stdio.h>
#include<stdlib.h>

int main()
{
//flag=1表示升序，flag=0表示降序
long n,m,i,j,k,t,*arr,flag=1;

scanf("%ld %ld",&n,&m);
arr=(long*)calloc(n+m,sizeof(long));
for(i=0;i<n;i++)
scanf("%ld",arr+i);
if(arr[0]>arr[n-1])
flag=0;
for(i=0;i<m;i++)
{
scanf("%ld",&t);
//printf("t=%ld\n",t);
for(j=0;j<n+i;j++)
{
if(((1==flag)&&t<arr[j])||((0==flag)&&t>arr[j]))
{
for(k=n+i-1;k>=j;k--)
arr[k+1]=arr[k];
break;
}
}
arr[j]=t;
}
for(i=0;i<n+m-1;i++)
printf("%ld ",arr[i]);
printf("%ld\n",arr[n+m-1]);
free(arr);
return 0;
}