189 8069 5689
要求：已知一个一维数组 arr ，现在要求将它向左旋转n个位置。
成都创新互联是一家专注网站建设、网络营销策划、小程序开发、电子商务建设、网络推广、移动互联开发、研究、服务为一体的技术型公司。公司成立十年以来，已经为上千多家集装箱各业的企业公司提供互联网服务。现在，服务的上千多家客户与我们一路同行，见证我们的成长；未来，我们一起分享成功的喜悦。
方法一：
假设允许开辟一个临时空间，那么问题就变得简单了，可以开辟一个跟arr长度相同的空间，然后隔n个位置不断添加元素即可，
思路比较简单，下面是代码实现：
void RotateLeft1(vector&arr, const int step) { vector ret; int sz = arr.size(); ret.resize(sz); for (int i = 0; i < arr.size(); ++i) { ret[ (sz + i - step) % sz ] = arr[i]; } arr = ret; }
方法二：
如果不允许开辟辅助空间，那就只能对现有的一维数组进行操作了，可以实现一个每次左移一位的函数RotateLStep()：
///// 之前的第一种方法由于要考虑new开辟的辅助空间的回收问题，数组使用了STL中的vector。而此处开始数组全部用传统的数组
void RotateLStep(int *arr, int sz) //向左移动一位
{
int first = arr[0];
for (int i = 0; i < sz - 1; ++i)
{
arr[i] = arr[i + 1];
}
arr[sz - 1] = first;
}
void RotateLeft2(int *arr, int sz, int step)
{
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] 的值
即可。
上代码：
///////////////////第三种方法
void RotateLeft3(int *arr, int sz, int step)
{
if (step == sz) //避免后面可能出现的死循环
{
return;
}
int tmp = arr[0];
int dst_index = 0;
int src_index = step;
int count = 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次交换即可，如下图：
提炼出的代码比较简单，具体如下：
/////////////////////第四种方法：
/////////////////////第四种方法：
void ReverseArr(int *arr, int begin, int end) //数组 begin 到 end 之间的部分 逆序
{
int *a = arr + begin;
int sz = end - begin + 1;
for (int i = 0; i < sz / 2; ++i) //注意！ 这个方法要比下面注释的那种方法效率高一倍！
{
int tmp = a[i];
a[i] = a[sz - 1 - i];
a[sz - 1 - i] = tmp;
}
/*while (begin < end)
{
int tmp = arr[begin];
arr[begin++] = arr[end];
arr[end--] = tmp;
}*/
}
void RotateLeft4(int *arr, int sz, int step)
{
ReverseArr(arr, 0, step - 1);
ReverseArr(arr, step, sz - 1);
ReverseArr(arr, 0, sz - 1);
}可以看出 每次逆序的时间复杂度分别为 O(step) O(N - step) O(N / 2)
总共的时间复杂度是一个略小于N的值，也是这个问题的的最优实现方式
（完）