设为首页收藏本站

中国膜结构网

 找回密码
 立即注册

QQ登录

只需一步,快速开始

膜结构车棚
膜结构车棚膜结构资质国产膜材 膜结构网中国膜结构协会
查看: 59|回复: 1

合并两个有序数组

[复制链接]
  • TA的每日心情
    开心
    2021-6-18 10:57
  • 签到天数: 1538 天

    [LV.Master]伴坛终老

    发表于 2021-5-22 16:20 | 显示全部楼层 |阅读模式
    合并两个有序数组
    问题描述
    有两个排序的数组a和b,内存在a的末尾有足够多的剩余空间容纳b
    实现一个函数将b中所有的数字插入到a,最终结果是有序的

    实现思路
    由于a、b两个数组已经排序,并且题目提示在a数组的末尾有足够多空间容纳b数组,因此我们将b数组赋值给a数组时,可以考虑从两个数组的末尾元素开始比较,每次比较a数组和b数组的最后一个元素,将较大的那个元素作为新的a数组的最后一个元素,这样时间复杂度为O(n),而空间复杂度为O(1)

    代码
    显示数组的函数
    1. #include<iostream>
    2. #include<cstdio>
    3. using namespace std;

    4. //显示数组
    5. void DisplayArray( char *arrayName, int *a, int len )
    6. {
    7.     if ( a== NULL || len <= 0)
    8.     {
    9.         cout<<"数组 "<<arrayName<<" 为空"<<endl;
    10.         return;
    11.     }
    12.     cout<<"Element in array : "<<arrayName<<endl;
    13.     for (int i = 0; i < len; i++)
    14.     {
    15.         cout<<a[i]<<" ";
    16.     }
    17.     cout<<endl;
    18. }
    复制代码
    1. [code][code]/*合并两个数组
    2. a:第一个数组,b:第二个数组
    3. totalalen, a数组中的总长度, alen:a数组实际长度,blen:b数组长度
    4. */
    5. void MergeArray(int *a, int *b,  int totalalen, int alen, int blen )
    6. {
    7.     //参数检查
    8.     if ( a== NULL || b== NULL  )
    9.     {
    10.         cout<<"输入数组为空,请检查"<<endl;
    11.         return;
    12.     }

    13.     if ( alen <= 0 || blen <= 0 || totalalen < alen+blen)
    14.     {
    15.         cout<<"输入数组长度错误,请检查"<<endl;
    16.         return;
    17.     }

    18.     int newidx = alen + blen - 1;//合并后数组的索引
    19.     int aidx = alen -1;//a数组的索引
    20.     int bidx = blen -1;//b数组的索引

    21.     while (aidx >= 0 && bidx >= 0)
    22.     {
    23.         if (a[aidx] > b[bidx] )
    24.             a[newidx--] = a[aidx--];
    25.         else
    26.             a[newidx--] = b[bidx--];
    27.     }

    28.     while ( bidx >= 0)
    29.     {
    30.         a[newidx--] = b[bidx--];
    31.     }
    32. }
    复制代码
    [/code][/code]
    回复


    http://www.mjgw.org/ 专业从事膜结构设计、制作加工、施工安装的膜结构工程服务,能够为客户提供专业的膜结构整体解决方案。做中国最好的膜结构综合服务平台。欢迎大家联系电话:198-7840-1958,QQ:463017170.
    相关关键词:膜结构车棚,膜结构车棚覆盖,膜结构车棚公司,膜结构车棚多少钱,膜结构车棚厂家,膜结构车棚价格,社区膜结构车棚,膜结构车棚膜布厂家 ,膜结构车棚哪家好,膜结构车棚多少钱一米,膜结构车棚报价,膜结构车棚哪里有,膜结构车棚定制,膜结构车棚安装,膜结构车棚设计,膜结构车棚电话,膜结构车棚加工,膜结构车棚膜布价格,膜结构车棚批发,膜结构车棚制造商,膜结构车棚生产厂家,膜结构车棚设计,膜结构车棚施工,膜结构车棚多少钱一平米,膜结构车棚订制,张拉膜车棚,张拉膜车棚覆盖,张拉膜车棚公司,张拉膜车棚多少钱,张拉膜车棚厂家,张拉膜车棚价格,社区张拉膜车棚,张拉膜车棚膜布厂家 ,张拉膜车棚哪家好,张拉膜车棚多少钱一米,张拉膜车棚报价,张拉膜车棚哪里有,张拉膜车棚定制,张拉膜车棚安装,张拉膜车棚设计,张拉膜车棚电话,张拉膜车棚加工,张拉膜车棚膜布价格,张拉膜车棚批发,张拉膜车棚制造商,张拉膜车棚生产厂家,张拉膜车棚设计,张拉膜车棚施工,张拉膜车棚多少钱一平米,张拉膜车棚订制,常用膜材品牌:德国杜肯、法国法拉利、德国海德斯、德国米乐、日本平岗、韩国秀博、比利时希运、美国赫虏伯、中国科宝、上海慧遥。

    使用道具 举报

  • TA的每日心情
    开心
    2021-6-18 10:57
  • 签到天数: 1538 天

    [LV.Master]伴坛终老

     楼主| 发表于 2021-5-22 16:21 | 显示全部楼层
    /测试代码
    void Test(char *testName, int *arra1, int *arra2, int len, int len1, int len2 )
    {
        if (testName == NULL )
        {
            return;
        }
        cout<<testName<<" begins."<<endl;
        cout<<"Befor merge"<<endl;
        DisplayArray("A",arra1, len1);
        DisplayArray("B", arra2, len2);

        MergeArray(arra1, arra2, len, len1, len2);
        cout<<"After merge"<<endl;
        if ( len1 > 0)
        {
            DisplayArray("A", arra1, len1+len2);
        }
        else
            cout<<"A 为空"<<endl;
    }




    //测试用例1,a、b数组一样长
    void Test1()
    {
        int a[10] = {1,3,5,7,9};
        int b[] = {2,4,6,8,10};
       
        Test("Test1", a, b, 10, 5, 5);
    }



    //测试用例2,a数组比b数组长
    void Test2()  
    {  
        int a[20]={1,2,3,7};  
        int b[]={4,5,6};  

        Test("Test2", a, b, 20, 4, 3);  
    }



    //测试用例3,a数组比b数组短
    void Test3()  
    {  
        int a[20]={0};  
        int b[]={1,2,3};  

        Test("Test3", a, b, 20, 1, 3);  
    }  


    //测试用例4,a数组为空
    void Test4()  
    {  
        int a[20];  
        int b[]={0};  

        Test("Test4", a, b, 20, 0, 1);  
    }  


    回复 支持 反对

    使用道具 举报

    您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则

    关闭

    推荐膜材品牌上一条 /6 下一条

    进口膜材 国产膜材 pvdf膜材ptfe膜材ETFE膜材
    最好的膜结构公司 一级膜结构资质 膜结构一级资质
    膜结构设计-膜结构十大品牌-etfe设计-充气膜结构
    诺科膜结构
    遨都膜结构设计
    中国膜结构网
    中国空间膜结构

    QQ|申请友链|手机版|中国膜结构论坛