简易信息网

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
查看: 9|回复: 0

算法有序数组合并---在空间足够的情况下,进行O(n)的合并 ...

[复制链接]

31

主题

50

帖子

203

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
203
发表于 2018-1-1 13:41:31 | 显示全部楼层 |阅读模式
最近看一本书上有一个面试题,  原题目是 有两个递增数组 A1 A2,   A1的内存空间足够长, 现在要求合并 A2到A1,并且要求移动次数最小 ,面试的时候 我们尽量要以
最高效的方式完成 ,下面是此题  O(n)解法。

[cpp] view plain copy
print?


  • ///合并  
  • 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--;  
  •     }  
  • }  


测试代码

[cpp] view plain copy
print?


  • 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<<"  " ;  
  • }  
  • cout<<endl;  


结果



  今天的心情非常美丽哦!!!
回复

使用道具 举报

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

本版积分规则

手机版|Comsenz Inc. ( 沪ICP备10006327号-1

GMT+8, 2018-1-19 15:23 , Processed in 0.044443 second(s), 21 queries .

Powered by Discuz! X3.1

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表