剑指offer5.1——O（n）的复杂度合并两个有序数组

  1 #include"iostream"
  2 #include"stdio.h"
  3 using namespace std;
  4 
  5 int* ArrayMerge(int *a,int aLen,int  *b,int bLen)
  6 {
  7     int aIndex=aLen-1,bIndex=bLen-1,newIndex=aLen+bLen-1;
  8 
  9     while(aIndex>=0&&bIndex>=0)
 10     {
 11         if(a[aIndex]>b[bIndex])
 12         {
 13             a[newIndex--]=a[aIndex--];
 14         }
 15         else
 16         {
 17             a[newIndex--]=b[bIndex--];
 18         }
 19     }
 20     while(aIndex>=0)
 21     {
 22         a[newIndex--]=a[aIndex--];
 23     }
 24     while(bIndex>=0)
 25     {
 26         a[newIndex--]=b[bIndex--];
 27     }
 28     return a;
 29 }
 30 
 31 void Test(char *testName,int *a,int aLen,int *b,int bLen,int *res,int aMaxLen)
 32 {
 33     if(testName!=nullptr)
 34         cout<<"the "<<testName<<" begin:";
 35     if(aLen+bLen>aMaxLen)
 36     {
 37         cout<<"out of range!"<<endl;
 38         return;
 39     }
 40     if(a==nullptr || b==nullptr)
 41     {
 42         cout<<"the one of two arrays is NULL!"<<endl;
 43         return;
 44     }
 45     if(aLen<0 || bLen<0)
 46     {
 47         cout<<"error input"<<endl;
 48         return;
 49     }
 50     int *getRes=ArrayMerge(a,aLen,b,bLen);
 51     int i;
 52     for(i=0;i<aLen+bLen;i++)
 53     {
 54       //  cout<<getRes[i]<<" ";
 55         if(res[i]!=getRes[i]) break;
 56     }
 57     if(i<aLen+bLen)
 58         cout<<"failed!"<<endl;
 59     else
 60         cout<<"passed!"<<endl;
 61 }
 62 
 63 //a数组全排在b数组前面
 64 void Test1()
 65 {
 66     int a[100]={1,2,3};//一定要指定a数组的大小
 67     int b[]={4,5,6};
 68     int res[]={1,2,3,4,5,6};
 69     Test("Test1",a,3,b,3,res,100);
 70 }
 71 //a数组和b数组混合
 72 void Test2()
 73 {
 74     int a[100]={1,4,5};
 75     int b[]={2,3,6};
 76     int res[]={1,2,3,4,5,6};
 77     Test("Test2",a,3,b,3,res,100);
 78 }
 79 //a数组为空
 80 void Test3()
 81 {
 82     int a[100]={};
 83     int b[]={2,3,6};
 84     int res[]={2,3,6};
 85     Test("Test3",a,0,b,3,res,100);
 86 }
 87 //b数组为空
 88 void Test4()
 89 {
 90     int b[]={};
 91     int a[100]={2,3,6};
 92     int res[]={2,3,6};
 93     Test("Test4",a,3,b,0,res,100);
 94 }
 95 
 96 //a、b数组为空
 97 void Test5()
 98 {
 99     int a[100]={};
100     int b[]={};
101     int res[]={};
102     Test("Test5",a,0,b,0,res,100);
103 }
104 //a、b数组为空
105 void Test6()
106 {
107     int *a=nullptr;
108     int b[]={};
109     int res[]={};
110     Test("Test6",a,0,b,0,res,100);
111 }
112 int main()
113 {
114     Test1();
115     Test2();
116     Test3();
117     Test4();
118     Test5();
119     Test6();
120     return 0;
121 }
View Code