温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

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

发布时间:2020-07-13 20:33:04 来源:网络 阅读:770 作者:shangluyi 栏目:编程语言

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


方法一:

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


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

思路比较简单,下面是代码实现:

void RotateLeft1(vector<int> &arr, const int step)
{
	vector<int> 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的值,也是这个问题的的最优实现方式


(完)

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI