首页 > 试题广场 >

有序序列合并

[编程题]有序序列合并
  • 热度指数:79978 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
输入两个升序排列的序列,将两个序列合并为一个有序序列并输出。

数据范围: , 序列中的值满足

输入描述:
输入包含三行,

第一行包含两个正整数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
int main()
{
    int m,n;
    scanf("%d %d", &m, &n);
    int num1[1000];
    int num2[1000];
    int num3[2000];
    int i;
    for (i = 0; i < m; i++)
    {
        scanf("%d", &num1[i]);
    }
    for (i = 0; i < n; i++)
    {
        scanf("%d", &num2[i]);
    }
    int j = 0;
    int k = 0;
    int x = 0;//j k是数组num1和num2的指针  x是数组num3的指针
    while (j < m && k < n)//两者都还有数时比较 较小的数放在num3 对比完后对应的指针要++
    {
        if (num1[j] < num2[k])
        {
            num3[x++] = num1[j++];
        }
        else
        {
            num3[x++] = num2[k++];
        }
    }
    while (j < m)//如果num1还有数 直接接着依次添加到num3
    {
        num3[x++] = num1[j++];
    }
    while (k < n)//如果num2还有数 直接接着依次添加到num3
    {
        num3[x++] = num2[k++];
    }
    for (i = 0; i < x; i++)
    {
        printf("%d ", num3[i]);
    }
}
发表于 2025-02-12 15:57:38 回复(0)
#include <stdio.h>
void merge(int arr1[], int arr2[], int n, int m) {
    int j = 0, k = 0, h = 0, flag = 0;
    int arr[2000] = { 0 };
    for (j = 0; j < m + n; j++) {
        if (arr1[k] <= arr2[h]) {
            arr[j] = arr1[k];
            k++;
            if (k == n) {
                flag = 1;
                break;
            }
        } else if (arr1[k] > arr2[h]) {
            arr[j] = arr2[h];
            h++;
            if (h == m) {
                flag = 2;
                break;
            }
        }
    }
    if (flag == 1) {
        for (j = n + h; j < n + m; j++) {
            arr[j] = arr2[h];
            h++;
        }
    }
    if (flag == 2) {
        for (j = m + k; j < n + m; j++) {
            arr[j] = arr1[k];
            k++;
        }
    }
    for (j = 0; j < n + m; j++) {
        printf("%d ", arr[j]);
    }

}

int main() {
    int n = 0, m = 0, i = 0;
    int arr1[1000] = { 0 };
    int arr2[1000] = { 0 };
    scanf("%d %d", &n, &m);
    for (i = 0; i < n; i++) {
        scanf("%d", &arr1[i]);
    }
    for (i = 0; i < m; i++) {
        scanf("%d", &arr2[i]);
    }
    merge(arr1, arr2, n, m);
    return 0;
}
发表于 2025-01-09 18:15:04 回复(0)
#include<stdio.h>
void My_scanf(int arr[], int x) //输入
{
    int i = 0;
    for(i=0;i<x;i++)
    {
        scanf("%d ",&arr[i]);
    }
}
void Sort(int arr3[],int n) //冒泡排序
{
    int i = 0;
    int j = 0;
    int g = 0;
    int temp = 0;
    for(i = 0; i< n-1;i++)
    {
        for(j=i+1;j<n;j++)
        {
           if(arr3[i]> arr3[j])
           {
              temp = arr3[i];
              arr3[i] = arr3[j];
              arr3[j] = temp;
           }
        }
    }

}
void combine(int arr1[],int arr2[],int arr3[],int n,int m)//合并两个数组
{
   int i = 0;
   int j = 0;
   for(i=0;i<n;i++)
   {
    arr3[i]=arr1[i];
   }
   for(j=0;j<m;j++)
   {
    arr3[j+n]=arr2[j];
   }
}
void My_printf(int arr3[],int k)//输出
{
    int i = 0;
    for(i=0;i<k;i++)
    {
        printf("%d ",arr3[i]);
    }
}
int main()
{
    int n =0;
    int m = 0;
    scanf("%d %d",&n,&m);
    int arr1[n];
    int arr2[m];
    int arr3[n+m];
    My_scanf(arr1,n);
    My_scanf(arr2,m);
    combine(arr1,arr2,arr3,n,m);
    Sort(arr3,n+m);
    My_printf(arr3,n+m);
    return 0;
}

发表于 2024-12-27 11:28:14 回复(0)
#include <stdio.h>
#include<string.h>
int main() {
    int n,m;
    scanf("%d %d",&n,&m);
    int arr1[1001]={0};
    int arr2[1001]={0};
    int i;
    int j;
    for(i=0;i<n;i++)
    {
        scanf("%d",&arr1[i]);
    }
    for(i=0;i<m;i++)
    {
        scanf("%d",&arr2[i]);
    }
    i=0;j=0;
    while(i<n&&j<m)
    {
        if(arr1[i]<arr2[j])
        {
            printf("%d ",arr1[i]);
            i++;
        }
        else
        {
            printf("%d ",arr2[j]);
            j++;
        }
    }
    if(i==n)
    {
        for(;j<m;j++)
        {
            printf("%d ",arr2[j]);
        }
    }
    else {
        for(;i<n;i++)
        {
            printf("%d ",arr1[i]);
        }
    }
    return 0;
}
发表于 2024-12-18 16:25:51 回复(0)
#include <stdio.h>
int main()
{
    int m,n,a[2000],i,j,temp;
    scanf("%d %d",&m,&n);
    for(i=0;i<m;i++){
        scanf("%d",&a[i]);
    }
    for(i=m;i<m+n;i++){
        scanf("%d",&a[i]);
    }
    for(i=0;i<n+m-1;i++){
        for(j=0;j<n+m-1-i;j++){
            if(a[j]>a[j+1]){
                temp=a[j];
                a[j]=a[j+1];
                a[j+1]=temp;
            }
        }
    }
    for(i=0;i<m+n;i++){
        printf("%d ",a[i]);
    }
    return 0;
}
发表于 2024-12-14 08:57:22 回复(0)
#include <stdio.h>

int main() {
    int n,m,tem=0;
    scanf("%d %d",&n,&m);
    int arr1[n];
    int arr2[m];
    int arr3[n+m];
    for(int i=0;i<n;i++){
        scanf("%d",&arr1[i]);
        arr3[i]=arr1[i];
    }
    for(int i=0;i<m;i++){
        scanf("%d",&arr2[i]);
        arr3[i+n]=arr2[i];
    }
    for(int u=0;u<n+m-1;u++){
        for(int j=0;j<n+m-1-u;j++){
            if(arr3[j]>arr3[j+1]){
                tem=arr3[j];
                arr3[j]=arr3[j+1];
                arr3[j+1]=tem;
            }
        }
    }
    for(int i=0;i<n+m;i++){
    printf("%d ",arr3[i]);
    }
    return 0;
}
发表于 2024-12-03 19:36:33 回复(0)
C语言
思路:先合并,然后排序
上代码
#include <stdio.h>
//冒泡排序
void hebing(int* arr,int sum)
{
    for(int i = 0;i<sum-1;i++)
    {
        for(int j = 0;j<sum-i-1;j++)
        {
            if(arr[j]>arr[j+1])
            {
                int temp =arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
            }
        }
    }
}
int main()
{
     int n = 0;
     int m = 0;
     scanf("%d %d",&n,&m);
     int arr1[1000];
     int arr2[1000];
     for(int i = 0;i<n;i++)
     {
        scanf("%d",&arr1[i]);
     }

      for(int i = 0;i<m;i++)
     {
        scanf("%d",&arr2[i]);
     }

     int arr[2000];
   //合并
     for(int i = 0;i<n+m;i++)
     {
         if(i<n)
         arr[i]=arr1[i];
         else
          arr[i]=arr2[i-n];
     }
     hebing(arr,n+m);    //排序
     
    for(int i = 0;i<n+m;i++)
     {
         printf("%d ",arr[i]);
     }
    return 0;
}

发表于 2024-11-22 21:06:27 回复(0)
#include <stdio.h>

int main() {
    int n=0, m=0;
    int i=0,j=0;
    scanf("%d %d",&n,&m);
    int arr[30000]={0};
    for(int i=0;i<n+m;i++){
        scanf("%d",&arr[i]);
    }
    //排序,排成升序
   for(i=0;i<n+m-1;i++){//比较的趟数
    for(j=0;j<n+m-1-i;j++){//每一趟比较的对数
        int tmp=0;
        if(arr[j]>arr[j+1]){//前一个数和后一个数比较
            tmp=arr[j];
            arr[j]=arr[j+1];
            arr[j+1]=tmp;
        }
    }
   }
   //输出
   for( i = 0;i<n+m;i++){
    printf("%d",arr[i]);
    if(i<n+m-1){//如果不是最后一个元素,打印空格
        printf(" ");
    }
   }
    return 0;
}

发表于 2024-11-16 19:17:21 回复(0)
#include <stdio.h>
int main() {
    int a, b;
    int i, x;
    int n, m;
    while (scanf("%d %d", &a, &b) != EOF) {
        int arr[a];
        int arr1[b];
        for (i = 0; i < a; i++) {
            scanf("%d", &arr[i]);
        }
        for (i = 0; i < b; i++) {
            scanf("%d", &arr1[i]);
        }
        x = a + b;
        n = a;
        m = b;
        a = b = 0;
        for (i = 0; i < x; i++) {
           
            if (arr[a] < arr1[b] && a < n ) {
                printf("%d ", arr[a]);
                a++;
            }
            else if(b < m){
                printf("%d ", arr1[b]);
                b++;
            }
            else{
                printf("%d", arr[a]);
            }
        }
    }
    return 0;
}
发表于 2024-09-13 18:09:42 回复(0)
#include<stdio.h>
int main()
{
	int n = 0;
	int m = 0;
	scanf("%d %d", &n, &m);
	int arr1[1001] = { 0 };
	int arr2[1001] = { 0 };
	int merged[2002] = { 0 };
	for (int i = 0; i < n; i++)//输入第一行的n个元素
	{
		scanf("%d", &arr1[i]);
	}
	for (int i = 0; i < m; i++)//输入第二行的m个元素
	{
		scanf("%d", &arr2[i]);
	}

    int i = 0;
    int j = 0;
    int k = 0;
    while (i < n && j < m)//由于题目中的两个数组是升序排列,右值一定大于左值,所以该循环最终的结果会以遇到某数组中一个巨大的值为上限,将另一数组遍历排序完
    {
        if (arr1[i] < arr2[j]) //升序排列两数组中的元素,当一组数据被彻底遍历完之后,另一组剩下的只有一些更大的值
        {
            merged[k++] = arr1[i++];
        }
        else 
        {
            merged[k++] = arr2[j++];
        }
    }

    //补漏,将上限值及其升序排列的所有右值添加到merged中  
    while (i < n) //当arr1里面还有值,陆续放到merged中
    {
        merged[k++] = arr1[i++];
    }
    while (j < m) //当arr2里面还有值,陆续放到merged中
    {
        merged[k++] = arr2[j++];
    }

    //如果题目改成无序数组,另加一个冒泡排序即可

    // 输出合并后的序列  
    for (int l = 0; l < k; l++)
    { 
        printf("%d ", merged[l]);
    }
    printf("\n"); 

	return 0;
}

发表于 2024-08-21 15:15:53 回复(0)
#include <stdio.h>

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    int arr1[n], arr2[m], arr3[n + m];

    for (int i = 0; i < n; i++) {
        scanf("%d", &arr1[i]);
    }
    for (int i = 0; i < m; i++) {
        scanf("%d", &arr2[i]);
    }

    int i = 0, j = 0, k = 0;
    while (i < n && j < m) {
        if (arr1[i] < arr2[j]) {
            arr3[k++] = arr1[i++];
        } else {
            arr3[k++] = arr2[j++];
        }
    }

    while (i < n) {
        arr3[k++] = arr1[i++];
    }
    while (j < m) {
        arr3[k++] = arr2[j++];
    }

    for (int i = 0; i < k; i++) {
        printf("%d ", arr3[i]);
    }

    return 0;
}

发表于 2024-08-16 11:16:55 回复(0)
#include <stdio.h>
#include <stdlib.h>

int * merge_sort(int arrn[], int arrm[], int n, int m);

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    int arrn[n];
    int arrm[m];
    int i = 0;
    while(i < n)
    {
        scanf("%d", &arrn[i]);
        i++;
    }
    i = 0;
    while(i < m)
    {
        scanf("%d", &arrm[i]);
        i++;
    }

    int * merge = NULL;
    merge = merge_sort(arrn, arrm, n, m);

    for(i = 0; i < n + m; i++)
    {
        printf("%d ", merge[i]);
    }
    free(merge);
    return 0;
}

int * merge_sort(int arrn[], int arrm[], int n, int m)
{
    int * merge = (int *)malloc((n + m) * sizeof(int));
    if (merge == NULL)
    {
        printf("Memory allocation failed\n");
        exit(1);
    }

    for(int num = 0; num < n + m; num++)
    {
        if (num < n)
        {
            merge[num] = arrn[num];
        }
        else
        {
            merge[num] = arrm[num - n];
        }
    }

    for(int i = 0; i < n + m - 1; i++)
    {
        for(int j = 0; j < n + m - 1 - i; j++)
        {
            if(merge[j] > merge[j + 1])
            {
                int temp = merge[j];
                merge[j] = merge[j + 1];
                merge[j + 1] = temp;
            }
        }
    }
    return merge;
}
发表于 2024-08-09 17:57:52 回复(0)
#include <stdio.h>
#include <stdlib.h>

int main() {
    int m, n;
    scanf("%d %d",&n, &m);

    //方法一,对于很大的数就效率比较低
    //时间复杂度为O((N+M)^2) 空间复杂度O(1)
    // int sum = m + n;
    // //申请m+n个大小的数组
    // int* a = (int*)malloc(sizeof(int)* (m + n));
    // for(int i = 0; i < sum; i++)
    // {
    //     scanf("%d", &a[i]);
    // }

    // //冒泡排序
    // for(int i = 0; i < sum - 1; i++)  //冒泡排序的趟数
    // {
    //     for(int j = 0; j < sum - 1 - i; j++)//一趟的交换次数
    //     {
    //         //升序
    //         if(a[j + 1] < a[j])
    //         {
    //             int tmp = a[j];
    //             a[j] = a[j + 1];
    //             a[j+1] = tmp;
    //         }
    //     }
    // }

    // //打印前五个数
    // for(int i = 0; i < m + n; i++)
    // {
    //     printf("%d ", a[i]);
    // }
    

    //方法二
    //以下代码vs能跑通过,这种是牺牲空间换时间的写法
    //时间复杂度为O(M + N),空间复杂度O(M+N)
    //申请三个数组
    int* a = (int*)malloc(sizeof(int) * (m+n));
    int* arr1 = (int*)malloc(sizeof(int) * n);
    int* arr2 = (int*)malloc(sizeof(int) * m);
    //输入数据
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &arr1[i]);
    }
    for(int i = 0; i < m; i++)
    {
        scanf("%d", &arr2[i]);
    }

    int p1, p2, p;
    p = p1 = p2 =0;
    //当有一个走完就得跳出来
    while (p1 < n && p2 <m) 
    {
        if(arr1[p1]  < arr2[p2])
        {
            // a[i] = arr1[p1];
            // p1++;
            a[p++] = arr1[p1++];
        }
        else
        {
            a[p++] = arr2[p2++];
        }
    }

    //还没走完的数组需要插入到数组a
    if(p1 == n) //数组arr1走完,说明数组arr2没走完
    {
        while (p2 < m)
        {
            a[p++] = arr2[p2++];
        } 
    }
    if(p2 == m)
    {
        while (p1 < n)
        {
            a[p++] = arr1[p1++];
        } 
    }

    //打印数组
    for(int i = 0; i < m+n; i++)
    {
        printf("%d ",a[i]);
    }
    //释放申请的空间
    free(a);
    free(arr1);
    free(arr2);
    a = arr1 = arr2 = NULL;
    return 0;
}


发表于 2024-06-22 13:41:35 回复(0)
#include <stdio.h>
int main() {
    int n,m,i,j;
    int arr1[1000],arr2[1000],arr3[2000];//创建三个数组,将n和m个数放入arr3,在进行冒泡排序
    scanf("%d %d", &n, &m);
    for(i=0;i<n;i++)
    {
        scanf("%d", &arr1[i]);
      arr3[i]=arr1[i];
    }
    for(j=0;j<m;j++)
    {
        scanf("%d", &arr2[j]);
        arr3[n+j]=arr2[j];
    }
    int a,b;
    for(a=0;a<n+m;a++)
    {
        int tmp=0;
        for(b=a;b<n+m;b++)
        {
            if(arr3[a]>arr3[b])
            {
                tmp=arr3[a];
                arr3[a]=arr3[b];
                arr3[b]=tmp;
            }
        }
    }
    for(int k=0;k<n+m;k++)
    {
        printf("%d ", arr3[k]);
    }
    return 0;
}
发表于 2024-06-07 11:48:58 回复(0)
#include <stdio.h>
#include<stdlib.h>

int com_int(const void* e1,const void* e2)
{
    return *(int*)e1-*(int*)e2;
}

void print(int pa[],int sz)
{
    int i=0;
    for(i=0;i<sz;i++)
    {
        printf("%d ",pa[i]);
    }
}

int main()
{
    int n=0;
    int m=0;
    int arr1[1000]={0};
    int arr2[1000]={0};
    int arr3[2000]={0};
    int i=0;
   
    scanf("%d %d",&n,&m);

    //输入第一组数
    for(i=0;i<n;i++)
    {
        scanf("%d",&arr1[i]);
    }

    //输入第二组数
    for(i=0;i<m;i++)
    {
        scanf("%d",&arr2[i]);
    }

    //将前两组数据导入第三组
    for(i=0;i<n+m;i++)
    {
        if(i>=n)
        {
            arr3[i]=arr2[i-n];
        }
        if(i<n)//可与上面else
        {
            arr3[i]=arr1[i];
        }
    }
    qsort(arr3,n+m,sizeof(arr3[0]),com_int);
    print(arr3,n+m);

    return 0;
}
发表于 2024-05-29 15:25:32 回复(0)
#include <stdio.h>

int main() {
    int n = 0, m=0;//个数
    scanf("%d %d", &n, &m);

    int a[2000]={0};
    //输入a组数据, 输入b组数据
    int i=0;
    for (i=0; i<n; i++)//输入个数为n的数据
    {
        scanf("%d", &a[i]);
    }
     for (int i=n; i<m+n; i++)//输入个数为m的数据
    {
        scanf("%d", &a[i]);
    }

    //排序
    for (int k = 1; k <n+m; k++)
    {
        for (i = 0; i < n+m-1; i++)
        {
            if (a[i] > a[i + 1])
            {
                int temp = a[i + 1];
                a[i + 1] = a[i];
                a[i] = temp;
            }
        }
    }

    //打印
    for (int j = 0; j < n+m; j++)
        {
            printf("%d ", a[j]);
        }
   

   
    return 0;
}
发表于 2024-05-10 11:58:30 回复(0)
#include <stdio.h>

    void merge_sorted_arrays(int* arr1,int n,int* arr2,int m,int* merged_sorted_arr)
{
    int i = 0;
    int j = 0;
    int k = 0;
    while (i < n && j < m)
    {
        if (arr1[i] < arr2[j])
            merged_sorted_arr[k++] = arr1[i++];
        else
            merged_sorted_arr[k++] = arr2[j++];
    }
    while (i < n)
    {
        merged_sorted_arr[k++] = arr1[i++];
    }
    while (j < m)
    {
        merged_sorted_arr[k++] = arr2[j++];
    }
}
int main()
{
    int n = 0;
    int m = 0;
    scanf("%d %d", &n, &m);
    int arr1[n] ;
    int arr2[m] ;
    int merged_sorted_arr[n + m] ;
    int i = 0;
    for (i = 0; i < n; i++)
    {
        scanf("%d", &arr1[i]);
    }
    for (i = 0; i < m; i++)
    {
        scanf("%d", &arr2[i]);
    }
    merge_sorted_arrays(arr1, n, arr2, m,merged_sorted_arr);
    for (i = 0; i < n + m; i++)
    {
        printf("%d ", merged_sorted_arr[i]);
    }
    return 0;
}
编辑于 2024-04-17 22:56:35 回复(0)
#include <stdio.h>
#include <stdlib.h>
void sort_merge(int *a,int *b,int n,int m)
{   
    int i,j,tem;
    for(i=0;i<m;i++)//合并两个数组
    *(a+i+n)=*(b+i);

    for(i=0;i<(m+n-1);i++)//冒泡排序
    {
        for(j=0;j<(m+n-i-1);j++)
        {
            if(*(a+j)>*(a+1+j))
            {
                tem = *(a+j);
                *(a+j) = *(a+1+j);
                *(a+1+j) = tem;
            }
        }
    }
}

int main() {
    int i,n,m;
    scanf("%d",&n);
    scanf("%d",&m);
   int *a = (int *)malloc((n+m)*sizeof(int));
   int *b = (int *)malloc(m*sizeof(int));

   for(i=0;i<n;i++)
        scanf("%d",a+i);
  
  for(i=0;i<m;i++)
    scanf("%d",b+i);

   sort_merge(a, b, n, m);

   for(i=0;i<(n+m);i++)
    printf("%d ",*(a+i));

    return 0;
}

编辑于 2024-04-07 15:51:23 回复(0)
#include <stdio.h>
int main()
{
	//arr1内的数据
	int n = 0;
	//arr2内的数据
	int m = 0;
	scanf("%d %d", &n, &m);
	int arr1[1000] = { 0 };
	int arr2[1000] = { 0 };
	int arr3[2000] = { 0 };
	//输入arr1的值
	int i = 0;
	for (i = 0; i < n; i++)
	{
		scanf("%d", &arr1[i]);
	}

	//输入arr2的值
	int j = 0;
	for (j = 0; j < m; j++)
	{
		scanf("%d", &arr2[j]);
	}
	//使下标都为0
	i = 0;
	j = 0;
	int k = 0;//arr3下标
	//开始比较
	while (i < n && j < m)
	{
		if (arr1[i] < arr2[j])
		{
			arr3[k] = arr1[i];
			i++;
			k++;
		}
		else
		{
			arr3[k] = arr2[j];
			j++;
			k++;
		}
	}
	//arr1遍历结束,需要将arr2中剩余的元素全部放入arr3中
	if (i == n)
	{
		while (j < m)
		{
			arr3[k] = arr2[j];
			j++;
			k++;
		}
	}
	else//arr2遍历结束,需要将arr1中剩余的元素全部放入arr3中
	{
		while (i < n)
		{
			arr3[k] = arr1[i];
			i++;
			k++;
		}
	}
	//打印arr3的数据
	i = 0;
	for (i = 0; i < n + m; i++)
	{
		printf("%d ", arr3[i]);
	}
	return 0;
}

发表于 2024-04-06 16:25:50 回复(0)