平武建站

完整解析题目：数组移位的实现，以及逐步优化

要求：已知一个一维数组 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://pwwzsj.com/article/pojeph.html

其他资讯