**最近看一本書上有一個面試題, ?原題目是 有兩個遞增數組 A1 A2, ? A1的內存空間足夠長, 現在要求合并 A2到A1,并且要求移動次數最小 ,面試的時候 我們盡量要以?** **最高效的方式完成 ,下面是此題 ?O(n)解法。** ~~~ ///合并 void MergeArray(int *arrA1,int *arrA2,int nLenA1,int nLenA2) { if(!arrA1||!arrA2) return ; //合并后的尾部 int *pBehandA1=(arrA1+nLenA1-1+nLenA2); int *pFrontA1=arrA1+nLenA1-1 ; int *pEndA2= arrA2+nLenA2-1; //循環次數 n 或者只剩下第二個數組 for(int i=nLenA1+nLenA2,j=nLenA2,k=nLenA1; i>0; i--) { if(j>0&&k>0) { //當A2 大于 A1 if(*pEndA2>=*pFrontA1) { *pBehandA1=*pEndA2 ; pEndA2-- ; j--; } //當A2小于 A1 else if(*pEndA2<*pFrontA1) { *pBehandA1=*pFrontA1 ; pFrontA1-- ; k--; } } //結束 else if(j<=0) { break; } //當前面數組合并完畢 else if(k<=0&&j>0) { *pBehandA1=*pEndA2 ; pEndA2-- ; j--; } pBehandA1--; } } ~~~ 測試代碼 ~~~ int *p1=new int[100] ; p1[0]=10; p1[1]=40; p1[2]=60; p1[3]=70; p1[4]=80; p1[5]=90; p1[6]=99; int *p2=new int[100] ; p2[0]=3; p2[1]=7; p2[2]=9; p2[3]=11; p2[4]=21; p2[5]=22; p2[6]=33; MergeArray(p2,p1,7,7); for(int i=0;i<14;i++){ cout<<p2[i]<<" " ; } cout<<endl; ~~~ 結果