[转]数组右移/左移计算时间复杂度最优化

已知一个长度为n的数组和一个正整数k,并且最多只能使用一个用于交换的附加空间单元,试设计算法得到原数组循环右移k次的结果,要求他的时间复杂度为 n(即与k无关):

一种比较简便的方法就是利用一个类似于德·摩根定律的方法,对于数组A,将它分为两截,分别为B和C,如果分别对B和C进行逆序操作,然后再对整个数组进行逆序操作,则就可达到左移k个位置的目的。

假设原数组序列为0123456,要求变换成的数组序列为4560123,即循环左移了4位。比较之后,不难看出,其中有两段的顺序是不变的:0123和456,可把这两段看成两个整体。左移K位的过程就是把数组的两部分交换一下。变换的过程通过以下步骤完成:

1.   逆序排列0123:0123456 → 3210456;

2.   逆序排列456:3210456 → 3210654;

3.   全部逆序:3210654 → 4560123。

这个过程可以被简单地证明。

并且时间复杂度为O(N)。

程序代码:

void Reverse(int *Arr, int Begin, int End)  

{  

     while(Begin < End)  //    以中心为对称点,分别交换对偶位置上的数  

     {  

         int Temp = Arr[Begin];  

         Arr[Begin] = Arr[End];  

         Arr[End] = Temp;  

         Begin++;  

         End--;  

     }  

}  

void Shift(int *Arr, int N, int k)  

{  

     Reverse(Arr, 0, k - 1);  

     Reverse(Arr, k, N - 1);  

     Reverse(Arr, 0, N - 1);  

}

发表评论

电子邮件地址不会被公开。 必填项已用*标注