要求：已知一个一维数组 arr ，现在要求将它向左旋转n个位置。


方法一：

假设允许开辟一个临时空间，那么问题就变得简单了，可以开辟一个跟arr长度相同的空间，然后隔n个位置不断添加元素即可，



思路比较简单，下面是代码实现：

voidRotateLeft1(vector<int>&arr,constintstep){vector<int>ret;intsz=arr.size();ret.resize(sz);for(inti=0;i<arr.size();++i){ret[(sz+i-step)%sz]=arr[i];}arr=ret;}

方法二：

如果不允许开辟辅助空间，那就只能对现有的一维数组进行操作了，可以实现一个每次左移一位的函数RotateLStep()：

/////之前的第一种方法由于要考虑new开辟的辅助空间的回收问题，数组使用了STL中的vector。而此处开始数组全部用传统的数组voidRotateLStep(int*arr,intsz)//向左移动一位{intfirst=arr[0];for(inti=0;i<sz-1;++i){arr[i]=arr[i+1];}arr[sz-1]=first;}voidRotateLeft2(int*arr,intsz,intstep){while(step--){RotateLStep(arr,sz);}}

但是显而易见，这种方法的效率太低了，RotateLStep()的时间复杂度为 O(N * N)


/*

优化：

数组长度为sz，那么向左移动n位就等价于向右移动(sz - n)位，那么可以比较并判断出需要移动步数较少的方向，以进一步提高效率

*/


方法三：

这个方法，在《编程珠玑》里，被叫做“杂技算法”，套路还是比较深的

具体的思路是：

先保存arr[0],然后把arr[0] = arr[step % sz]

然后 arr[step % sz] = arr[2*step % sz]

然后 arr[2step % sz] = arr[3*step % sz]

......

循环结束的条件为 运行 sz - 1 次

最后一次，让当前的目标索引的值 = 最开始保存的 arr[0] 的值

即可。


上代码：

///////////////////第三种方法voidRotateLeft3(int*arr,intsz,intstep){if(step==sz)//避免后面可能出现的死循环{return;}inttmp=arr[0];intdst_index=0;intsrc_index=step;intcount=sz;while(--count)//移动了sz次（加上最底下那一次），或者说，时间复杂度是O（N）{arr[dst_index%sz]=arr[src_index%sz];dst_index+=step;src_index+=step;}arr[dst_index%sz]=tmp;}

可以看出，程序执行的过程中，对数组内的元素移动，或者说赋值了 sz 次,

所以这个方法的时间复杂度是 O(N)，并且不需要开辟辅助空间，是一种比较高效的算法了



方法四：

从向量的角度思考这个问题： （题设： 数组 0 1 2 3 4 5 6 7， 左移3位）

可以把这个数组 分成3部分： a 、b1 、b2




接下来，做以下几件事：

1：交换 a 和 b2 ，得到 b2 b1 a向量（这一步执行完，a 已经 放在了 最终的位置）

2: 交换b1 b2 的位置,得到 b1 b2 a 向量，也是最终我们需要的数组

以上为推论，将这些交换步骤中相似的部分总结归纳，问题就变得很简单，只需要3次交换即可，如下图：


提炼出的代码比较简单，具体如下：

/////////////////////第四种方法：/////////////////////第四种方法：voidReverseArr(int*arr,intbegin,intend)//数组begin到end之间的部分逆序{int*a=arr+begin;intsz=end-begin+1;for(inti=0;i<sz/2;++i)//注意！这个方法要比下面注释的那种方法效率高一倍！{inttmp=a[i];a[i]=a[sz-1-i];a[sz-1-i]=tmp;}/*while(begin<end){inttmp=arr[begin];arr[begin++]=arr[end];arr[end--]=tmp;}*/}voidRotateLeft4(int*arr,intsz,intstep){ReverseArr(arr,0,step-1);ReverseArr(arr,step,sz-1);ReverseArr(arr,0,sz-1);}


可以看出 每次逆序的时间复杂度分别为 O(step) O(N - step) O(N / 2)

总共的时间复杂度是一个略小于N的值，也是这个问题的的最优实现方式


（完）