学步园

from:http://blog.csdn.net/livelylittlefish/article/details/2102457

来源：http://topic.csdn.net/u/20071228/16/cbc82a28-7288-411e-bf0f-caeec50756bf.html

输入a_1,   a_2,   ...,   a_n,   b_1,   b_2,   ...,   b_n，如何在O(n)的时间，用O(1)的空间，将这个序列顺序改为a_1,   b_1,   ...,   a_n,   b_n。 ==================================================================================

已经回帖，但为与朋友们交流方便并保证探讨的连续性，在此再次总结我的算法。请各位朋友指正。

算法思想如下：

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

      a1   a2   a3   a4   a5   a6   a7   a8   a9   |   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   b1   a3   a4   a5   a6   a7   a8   b8   |   a2   b2   b3   b4   b5   b6   b7   a9   b9

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

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

2. 左边从位置left=3开始，右边从位置n+1开始，向右交换count=2个元素，即a3   a4   和   a2   b2交换

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

    序列变为：

      a1   b1   a2   b2   a5   a6   a7   b6   b7   |   a3   a4   b3   b4   b5   a8   b8   a9   b9

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

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

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

    序列变为：

      a1   b1   a2   b2   a5   a6   a7   a3   a4   |   b6   b7   b3   b4   b5   a8   b8   a9   b9

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

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

    序列变为：

      a1   b1   a2   b2   a3   a4   a5   a6   a7   |   b3   b4   b5   b6   b7   a8   b8   a9   b9

5.至此，将原来的序列缩小为：

      a3   a4   a5   a6   a7   |   b3   b4   b5   b6   b7

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

    为方便比较，序列变化如下：

      a1   a2   a3   a4   a5   a6   a7   a8   a9   |   b1   b2   b3   b4   b5   b6   b7   b8   b9

      a1   b1   a3   a4   a5   a6   a7   a8   b8   |   a2   b2   b3   b4   b5   b6   b7   a9   b9

      a1   b1   a2   b2   a5   a6   a7   b6   b7   |   a3   a4   b3   b4   b5   a8   b8   a9   b9

      a1   b1   a2   b2   a3   a4   a5   a6   a7   |   b3   b4   b5   b6   b7   a8   b8   a9   b9

源程序如下：

/************************************************************************
 * 输入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=0;    //交换次数
int movetimes=0;        //移动次数

//交换两个数据
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=0;i<x;i++)
    {
        t=a[0];
        for(int j=0;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=0;i<x;i++)
    {
        t=a[n-1];
        for(int j=n-1;j>0;j--)
            a[j]=a[j-1];
        a[0]=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=0;j<count;j++)
            swap(a+left+j,a+n+j);

        //若notmatch=0,该交换不能进行,否则为重复交换
        if(notmatch>0)
        {
            for(j=0;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)
    {
        count/=2;

        //由中间对称交换count个数据
        for(int j=0;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);
    }
}

//显示菜单
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=0; i<n;i++)
        printf("%3d",a[i]);
    printf(" ");
}

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

    for(i=0;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")!=0)
    {
        if(stricmp(sinput,"i")==0)
        {
            printf("  please input n:");
            scanf("%d",&n);

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

            display(a,2*n);

            exchangetimes=0;
            movetimes=0;

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

            printf("   exchange times: %d ",exchangetimes);
            printf("  move times: %d ",movetimes);
        }
        else if(stricmp(sinput,"t")==0)
        {
            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=0; j<2*i;j++)
                    a[j]=j+1;

                exchangetimes=0;
                movetimes=0;
                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);
    }
}

为方便讨论，贴出两个运行结果的图片：

1. 输入n

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

from：http://blog.csdn.net/livelylittlefish/article/details/2102537

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

交换次数变化

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

左边向右交换，右边向左交换

算法思想：

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

   a1 a2 a3 a4 a5 a6 a7 a8 a9 | 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 b1 a3 a4 a5 a6 a7 a8 b8 | a2 b2 b3 b4 b5 b6 b7 a9 b9

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

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

2.左边从位置left=3开始，右边从位置n+1开始，向右交换count=2个元素，即a3 a4 和 a2 b2交换

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

  序列变为：

   a1 b1 a2 b2 a5 a6 a7 b6 b7 | a3 a4 b3 b4 b5 a8 b8 a9 b9

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

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

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

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

  序列变为：

   a1 b1 a2 b2 a5 a3 b3 a4 b4 | a6 b6 a7 b7 b5 a8 b8 a9 b9

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

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

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

  序列变为：

   a1 b1 a2 b2 a3 b3 a4 b4 a5 | b5 a6 b6 a7 b7 a8
b8 a9 b9

5.至此，将原来的序列缩小为：

      a5 | b5

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

为方便比较，序列变化如下：

a1 a2 a3 a4 a5 a6 a7 a8 a9 | b1 b2 b3 b4 b5 b6 b7 b8 b9

       a1 b1 a3 a4 a5 a6 a7 a8 b8 | a2 b2 b3 b4 b5 b6 b7 a9 b9

       a1 b1 a2 b2 a5 a6 a7 b6 b7 | a3 a4 b3 b4 b5 a8 b8 a9 b9

       a1 b1 a2 b2 a5 a3 b3 a4 b4 | a6 b6 a7 b7 b5 a8 b8 a9 b9

       a1 b1 a2 b2 a3 b3 a4 b4 a5 | b5 a6 b6 a7 b7 a8 b8 a9 b9

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

若lefta³count，如n=9，交换到左边的b可以配对（同时，交换到右边的a也配对），故只需将这些数据循环左移notmatch位；

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

时间复杂度：

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

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

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

源代码如下：

/************************************************************************
 * 输入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=0;    //交换次数
int movetimes=0;        //移动次数

//交换两个数据
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=0;i<x;i++)
    {
        t=a[0];
        for(int j=0;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=0;i<x;i++)
    {
        t=a[n-1];
        for(int j=n-1;j>0;j--)
            a[j]=a[j-1];
        a[0]=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=0;j<count;j++)
            swap(a+left+j,a+n+j);

        //若notmatch=0,该交换不能进行,否则为重复交换
        if(notmatch>0)
        {
            for(j=0;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<0)
    {
        count/=2;

        //由中间对称交换count个数据
        for(int j=0;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=0;j<count;j++)
            swap(a+n-count+j,a+n+j);

        //递归调用中间对称的count个数据
        exchange(a+n-count,count);
        exchange(a+n,count);
        
        if(notmatch>0)
        {
            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=0; i<n;i++)
        printf("%3d",a[i]);
    printf(" ");
}

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

    for(i=0;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")!=0)
    {
        if(stricmp(sinput,"i")==0)
        {
            printf("  please input n:");
            scanf("%d",&n);

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

            display(a,2*n);

            exchangetimes=0;
            movetimes=0;

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

            printf("   exchange times: %d ",exchangetimes);
            printf("  move times: %d ",movetimes);
        }
        else if(stricmp(sinput,"t")==0)
        {
            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=0; j<2*i;j++)
                    a[j]=j+1;

                exchangetimes=0;
                movetimes=0;
                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比较，移动次数明显减少，交换次数下降不明显。