Problem Solving using C++

Algorithm Study using C++

求两排序数组的中位数

#include <iostream>
#include 
<string>

using namespace std;

int main(int argc,char* argv[])
{
    
int A[]={1,3,5,7,8,9};
    
int B[]={2,4,6,10,11,12,13,14};

    
int sizeA = sizeof(A)/sizeof(int);
    
int sizeB = sizeof(B)/sizeof(int);

    
int ma=0,na=sizeA-1;
    
int mb=0,nb=sizeB-1;

    
while(1)
    {
        
int ka=(na+ma+1)/2;
        
int kb=(nb+mb+1)/2;

        
if(na<ma)
        {
            cout
<<B[kb]<<endl;
            
break;
        }
        
if(nb<mb)
        {
            cout
<<A[ka]<<endl;
            
break;
        }
        
if(A[ka]==B[kb])//find the value
        {
            cout
<<A[ka]<<endl;
            
break;
        }

        
if((ma==na)&&((nb-mb+1)%2==0))//there is only one element at A[]
        {
            
if((A[na]<B[kb])&&(A[na]>=B[kb-1]))
            {
                cout
<<A[na]<<endl;
                
break;
            }
        }
        
if((ma==na)&&((nb-mb+1)%2))
        {
            
if((A[na]>B[kb])&&(A[na]<=B[kb+1]))
            {
                cout
<<A[na]<<endl;
                
break;
            }
        }

        
if((mb==nb)&&((na-ma+1)%2==0))//there is only one element at B[]
        {
            
if((B[nb]<A[ka])&&(B[nb]>=A[ka-1]))
            {
                cout
<<B[nb]<<endl;
                
break;
            }
        }
        
if((mb==nb)&&((na-ma+1)%2))
        {
            
if((B[nb]>A[ka])&&(B[nb]<=A[ka+1]))
            {
                cout
<<B[nb]<<endl;
                
break;
            }
        }

        
int offset=ka-ma;
        
if(offset>(kb-mb))
            offset
=kb-mb;
        
if(offset==0)
            offset
++;
        
//int offset=((ka>=kb)?ka:kb);

        
if(A[ka]<B[kb])
        {
            ma
+=offset;
            nb
-=offset;
        }

        
if(A[ka]>B[kb])
        {
            na
-=offset;
            mb
+=offset;
        }
    }

    system(
"pause");
    
return 0;
}

posted on 2007-08-31 10:32 Kingoal Lee's Alogrithm Study using cplusplus 阅读(894) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


My Links

Blog Stats

常用链接

留言簿(1)

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜