完整解析题目:数组移位的实现,以及逐步优化
要求:已知一个一维数组 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的值,也是这个问题的的最优实现方式
(完)
本文标题:完整解析题目:数组移位的实现,以及逐步优化
标题链接:http://scyanting.com/article/pojeph.html