google面试题及我的算法(1)——交叉换位(改进)

晨曦之光 发布于 2012/03/09 14:14
阅读 166
收藏 1

对“一道google面试题及我的算法(1) ”(简称算法1)的改进

交换次数变化

对算法1还可以再改进。例如,N=9时,第2步执行后,实际上中间位置的两边对称的4个元素基本配对,只需交换中间的两个元素即可,如下表所示。颜色表示每次要交换的元素

左边向右交换,右边向左交换

 

算法思想:

N=9为例(中间的竖表示中间位置):

   a 1 a 2 a 3 a 4 a 5 a 6 a 7 a 8 a 9 | b1 b2 b3 b4 b5 b6 b7 b8 b9

  头尾的元素不需任何操作

1.左边从位置left=2开始,右边从位置n+1开始,向右交换count=1个元素,即a2,b1交换

  右边从位置right=2n-1开始,左边从位置n开始,向左交换count=1个元素,即b8,a9交换

  序列变为:

   a1 b 1 a 3 a 4 a 5 a 6 a 7 a 8 b8 | a2 b2 b3 b4 b5 b6 b 7 a 9 b9

  故已经成功放好位置的有(a1,b1),(a9,b9)

  其中(a8,b8),(a2,b2)也配对,只需将其交换到相应的位置即可

2.左边从位置left=3开始,右边从位置n+1开始,向右交换count=2个元素,即a 3 a 4 a2 b2交换

  右边从位置right=2n-2开始,左边从位置n开始,向左交换count=2个元素,即b6 b7 a8 b8交换

  序列变为:

   a1 b 1 a 2 b 2 a 5 a 6 a 7 b6 b7 | a 3 a 4 b3 b4 b 5 a 8 b 8 a 9 b9

  故又成功放好位置的有(a2,b2),(a8,b9)

  其中(a6,a7,b6,b7),(a3,a4,b3,b4)只需交换中间两个元素也配对,只需将其交换到相应的位置即可 

3.左边从位置left=5开始,右边从位置n开始,已不能满足交换count=4个元素的要求,故退出循环

  从中间位置对称交换count=4个元素

  序列变为:

   a1 b 1 a 2 b 2 a 5 a 3 b 3 a 4 b4 | a6 b 6 a 7 b7 b 5 a 8 b 8 a 9 b9

  此时只需将配对成功的(a3,b3),(a4,b4),(a6,b6),(a7,b7)移动相应的位置即可

4.左边从位置left=5开始的size=n-left+1=5个元素循环左移1

  右边从位置n+1开始的size=5个元素循环右移1

  序列变为:

   a1 b 1 a 2 b 2 a 3 b 3 a 4 b 4 a 5 | b 5 a 6 b 6 a 7 b 7 a 8 b 8 a 9 b9

5.至此,将原来的序列缩小为:

      a5 | b5

对该序列进行上述操作,直到所有元素都放到正确的位置

 

为方便比较,序列变化如下:

a 1 a 2 a 3 a 4 a 5 a 6 a 7 a 8 a 9 | b1 b2 b3 b4 b5 b6 b7 b8 b9

       a1 b 1 a 3 a 4 a 5 a 6 a 7 a 8 b8 | a2 b2 b3 b4 b5 b6 b 7 a 9 b9

       a1 b 1 a 2 b 2 a 5 a 6 a 7 b6 b7 | a 3 a 4 b3 b4 b 5 a 8 b 8 a 9 b9

       a1 b 1 a 2 b 2 a 5 a 3 b 3 a 4 b4 | a6 b 6 a 7 b7 b 5 a 8 b 8 a 9 b9

       a1 b 1 a 2 b 2 a 3 b 3 a 4 b 4 a 5 | b 5 a 6 b 6 a 7 b 7 a 8 b 8 a 9 b9

 

该方案需要判断lefta与该次交换个数count的关系:

lefta⊃3;count,如n=9,交换到左边的b可以配对(同时,交换到右边的a也配对),故只需将这些数据循环左移notmatch位;

lefta<count,如n=7,交换到左边的b不能配对(同时,交换到右边的a也不配对),故要将左边不能配对的b和右边不能配对的a交换,如上表所示,然后再将左边没有配对的a循环左移lefta位,将右边没有配对的b循环右移lefta位;

时间复杂度:

该算法的主要时间有两个:交换和移动,交换次数为T1=o(n),移动次数计算如下:
n=1+1+2+4+8+...+2k+(2k+c)=2k+1+2k+c
对2k+c个元素循环移动c次,共移动T2=c(2k+c)次,其中c<2k,如果c=2k,则不需任何移动,交换即可完成,即T2=0;
故2k+1<n<2k+1+2k+2k,即2k+1<n<2k+2, T2<2k * (2k + 2k)=22k+1<n2/2

虽然说移动的元素已经减至最少,但因该两个算法均有数据移动,其效率应该是O(n2)

================================================================================

源代码如下:

/************************************************************************
 * 输入a1,a2,...,an,b1,b2,...,bn
 * 在O(n)的时间,O(1)的空间
 * 将这个序列顺序改为a1,b1,a2,b2,a3,b3,...,an,bn
***********************************************************************
*/


#include 
< stdio.h >
#include 
< string .h >
#include 
< CONIO.H >

#define  MAXSIZE 2*1000

int  exchangetimes = ;     // 交换次数
int  movetimes = ;         // 移动次数

// 交换两个数据
void  swap( int   * x, int   * y)
{
    
int t;
    t
=*x;
    
*x=*y;
    
*y=t;

    exchangetimes
++;
}


// 将数组中的元素循环左移x位,n为数组的元素个数
void  rotate_left( int  a[], int  n, int  x)
{
    
int t;
    
for(int i=;i<x;i++)
    
{
        t
=a[];
        
for(int j=;j<n-1;j++)
            a[j]
=a[j+1];
        a[n
-1]=t;
    }


    movetimes
+=n*x;
}


// 将数组中的元素循环右移x位,n为数组的元素个数
void  rotate_right( int  a[], int  n, int  x)
{
    
int t;
    
for(int i=;i<x;i++)
    
{
        t
=a[n-1];
        
for(int j=n-1;j>;j--)
            a[j]
=a[j-1];
        a[
]=t;
    }


    movetimes
+=n*x;
}


// 按要求交换序列(假设元素从下标1开始存放)
void  exchange( int  a[], int  m)
{
    
int n=m/2;

    
if(n==1)        //a1,b1 ==>不需交换
        return;
    
else if(n==2)    //a1,a2,b1,b2 ==>只需交换中间的两个数据
    {
        swap(a
+1,a+2);
        
return;
    }


    
int done;        //已经处理的数据个数
    int left;        //左边开始交换的位置
    int right;        //右边开始交换的位置
    int count;        //每次交换的数据个数
    int lefta;        //左边未处理的a个数
    int notmatch;    //左边未匹配的a个数

    
//初始化
    done=1;
    left
=1;            //左边从位置1开始向右交换
    right=2*n-2;    //右边从位置2*n-2开始向左交换
    count=1;        //每次交换count个数据
    lefta=notmatch=n-1;

    
do
    
{        
        
//交换连续的count个元素
        for(int j=;j<count;j++)
            swap(a
+left+j,a+n+j);

        
//若notmatch=0,该交换不能进行,否则为重复交换
        if(notmatch>)
        
{
            
for(j=;j<count;j++)
                swap(a
+right-j,a+n-1-j);
        }

        
else
            
break;

        
//交换后将其调整为要求的序列
        if(count>=4)
        
{
            exchange(a
+left,count);
            exchange(a
+right-count+1,count);
        }


        
//重新调整各变量
        done+=count;
        lefta
=n-done-count;
        notmatch
=lefta-count;

        left
=left+count;
        right
=right-count;

        count
*=2;

        
if(notmatch<count)
            
break;
    }
while(1);

    
if(notmatch<)
    
{
        count
/=2;

        
//由中间对称交换count个数据
        for(int j=;j<count;j++)
            swap(a
+n-count+j,a+n+j);
        
        
int size=n-left;
        
//左边的数据循环左移lefta位
        rotate_left(a+left,size,lefta);

        
//右边的数据循环右移lefta位
        rotate_right(a+n,size,lefta);

        
int newm=2*size;
        
//递归调用
        exchange(a+left,newm);
    }

    
else    //if(notmatch<count)
    {
        
//由中间对称交换count个数据
        for(int j=;j<count;j++)
            swap(a
+n-count+j,a+n+j);

        
//递归调用中间对称的count个数据
        exchange(a+n-count,count);
        exchange(a
+n,count);
        
        
if(notmatch>)
        
{
            
int size=n-left;
            
//左边的数据循环左移notmatch位
            rotate_left(a+left,size,notmatch);

            
//右边的数据循环右移notmatch位
            rotate_right(a+n,size,notmatch);

            
int newm=2*notmatch;
            
//递归调用
            exchange(a+left+count,newm);
        }

    }

}


// 显示菜单
void  show_menu()
{
    printf(
"--------------------------------------------- ");
    printf(
"input command to test the program ");
    printf(
"   i or I : input n to test ");
    printf(
"   t or T : test program ");
    printf(
"   q or Q : quit ");    
    printf(
"--------------------------------------------- ");
    printf(
"$ input command >");
}


// 显示数据
void  display( int  a[], int  n)
{
    
for(int i=; i<n;i++)
        printf(
"%3d",a[i]);
    printf(
" ");
}


// 检查交换是否正确
bool  check( int  a[], int  n)
{
    
int i;

    
for(i=;i<n-2;i+=2)
    
{
        
if(a[i]!=i/2+1)
            
return false;
    }


    
for(i=1;i<n-1;i+=2)
    
{
        
if(a[i]!=(n+i+1)/2)
            
return false;
    }


    
return true;
}


void  main()
{
    
int a[MAXSIZE];
    
int n;
    
char sinput[10];

    show_menu();

    scanf(
"%s",sinput);
    
while(stricmp(sinput,"q")!=)
    
{
        
if(stricmp(sinput,"i")==)
        
{
            printf(
"  please input n:");
            scanf(
"%d",&n);

            
//假设数组的第0个元素为0,且不对其进行操作
            
//且假设数组中的数据为1,2,3,...,n,n+1,n+2,...,2n
            for(int i=; i<2*n;i++)    //初始化
                a[i]=i+1;

            display(a,
2*n);

            exchangetimes
=;
            movetimes
=;

            
//交换
            exchange(a,2*n);
            display(a,
2*n);

            printf(
"   exchange times: %d ",exchangetimes);
            printf(
"  move times: %d ",movetimes);
        }

        
else if(stricmp(sinput,"t")==)
        
{
            
int n1,n2;
            printf(
"  please input the begin number:");
            scanf(
"%d",&n1);
            printf(
"  please input the end number:");
            scanf(
"%d",&n2);

            printf(
"  press any key to start ... ");
            getch();

            
for(int i=n1;i<=n2;i++)
            
{
                
//初始化
                for(int j=; j<2*i;j++)
                    a[j]
=j+1;

                exchangetimes
=;
                movetimes
=;
                exchange(a,
2*i);

                
if(check(a,2*i))
                    
//printf("  n=%d ... ok! ",i);
                    printf("  n=%d ... ok!    exchange times: %d   move times: %d ",i,exchangetimes,movetimes);
                
else
                    printf(
"  n=%d ... wrong! ",i);
            }


            printf(
" ");
        }


        
//输入命令
        printf("$ input command >");
        scanf(
"%s",sinput);
    }

}

为方便比较,贴出与“一道google面试题及我的算法(1) ”相同的测试

1. 输入n

 

2. 测试从n1~n2的所有n是否能正确运行,并提供其交换次数和移动次数

===============================================================================

通过与算法1比较,移动次数明显减少,交换次数下降不明显。


原文链接:http://blog.csdn.net/livelylittlefish/article/details/2102537
加载中
返回顶部
顶部