问题:将一个n元一维向量向左旋转i个位置。例如,当n=8,且i =3时,向量abcdefgh旋转为defghabc.简单的代码使用一个n元向量在n步内完成该工作。
你能否仅仅使用数十个额外字节的存储空间,在此正比于n的时间内完成向量的旋转?

方案1:
首先将n的前i个数组复制到一个临时数组中,然后将剩余下的n-i个元素向左移动i个位置,最后将最初的i个元素存储在临时数组中的内容复制到n中余下的位置。
这个方案产生过大的存储空间消耗。

方案2:定义一个函数将n向左旋转一个位置,然后调用该函数i次。
该方法产生过多的时间消耗

方案3:将问题看作是交换向量AB的两段,得到向量BA。这里A代表n中的前i个元素.假设A比B短,将B分为Bl和Br,使得Br具有和A相同的长度,交换A,Br,得到BrBlA,A放到了他需要的最终位置。
接下来将BrBl看作整体,采用同样的形式,交换Br到Bl后面,递归解决
该方案非常优雅,效率也足够高。不过需要作者具有较好的编码能力

方案4:
将问题看作是把数组AB转换成BA,同时假定我们拥有一个函数可以将数组中的特定部分的元素求逆。
从AB开始------->对A求逆得到ArB
abc | defgh-----------> cba | defgh

对B求逆-------->ArBr
cba | defgh---------->cba | hgfed

对该式子整体求逆------------>(ArBr)r==BA
cba | hgfed---------->cbahgfed -----------> cbah | gfed---求逆--->defghabc (这就是我们要的结果)

最终得到BA.
defghabc

于是我们得到了如下代码;
reverse(0,i-1); /*逆转A*/
reverse(i
-1,n-1);/*逆转B*/
reverse(
0,n-1);/*逆转ArBr*/
时间和空间上都很高效,代码简短优雅,不易出错(强壮性高)