数组循环左移最优算法:逆置算法

优雅的算法 TOMORROW 4个月前 (08-24) 434次浏览 2个评论 扫描二维码
文章目录[隐藏]

设将 n 个整数存放到一维数组 R 中。试设计一个在时间和空间两方面都尽可能高效的算法,将 R 中的元素序列循环左移 p 个位置。

该问题的一个最优解为逆序算法。具体算法设计思路、时间复杂度与空间复杂度分析及算法源码(C 语言)如下。

算法设计

  • 首先,将数组分为两部分 a、b,a 表示前 p 个元素,b 代表剩下的元素;
  • 那么原问题就可以看作是:将数组 ab 转换成 ba;
  • 然后,将数组 R 中的 a、b 分别逆置得到 a-1b-1 
  • 然后对 a-1b-1 整体逆置就可以得到(a-1b-1 -1=ba;

 

举个例子:

将 abcdefg 循环左移 3 位:

  • 将 abcdefg 分成 abc、defg 两部分;
  • 然后将两部分分别逆置然后组合得到 cba gfed;
  • 再将 cba gfed 整体逆置就可以得到 defgabc;
  • 这样就完成了将 abcdefg 循环左移 3 位;

 

算法源码实现

以上算法的 C 语言实现:

/*数组循环左移——逆置算法*/
void reverse(int R[], int from, int to )
{
	int i ,temp ;
	for(i=0; i<(to-from+1)/2; i++)
	{
		temp = R[from+i];
		R[from+i] = R[to-i];
		R[to-i] = temp;
	}
}

void shift(int R[], int n, int p )
{
	reverse(R, 0, p-1);
	reverse(R, p, n-1);
	reverse(R, 0, n-1);
}

 

复杂度分析

时间复杂度

三个 reverse 函数的时间复杂度分别是 O(p/2)、O((n-p)/2)、O(n/2),

所以算法时间复杂度为 O(n)。

 

空间复杂度

而空间复杂度就是 O(1)

 

不是最优解的算法

借助辅助数组来解决问题:

算法思想:

  • 借助一个大小为 p 的辅助数组 S,将数组 R 中的前 p 个元素一次暂存于 S 中;
  • 然后将 R 中剩余的其他元素左移 p 位;
  • 再将数组 S 中的元素一次存回 R 中的后续位置;

 

时间复杂度和最优解的一样,都是 O(n);

但是由于使用了辅助数组,所以空间复杂度为 O(p)。

 

小结

在算法设计过程中,如果所设计的算法时间复杂度很高达不到要求,且所需算法对空间复杂度要求不高时:

通常往 牺牲空间复杂度换取更小的时间复杂度 方向思考,可以很快地将问题解决。

 

 


TOMORROW 星辰 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:数组循环左移最优算法:逆置算法
喜欢 (0)
TOMORROW
关于作者:
TOMORROW星辰第一作者。如有疑问或者发现错误,请留言作者。
寒冷的草丛发表我的评论  如需接收评论回复通知,请填写正确的 个人信息
取消评论
表情 加粗 斜体 签到
(2)个小伙伴在吐槽
  1. 博主的代码高亮用的是插件吗?
    独特的睫毛膏2018-08-24 21:26 回复 Windows 10 | Chrome 68.0.3440.75
    • TOMORROW
      对的,pure highlight
      TOMORROW2018-08-24 23:43 回复 Windows 10 | 搜狗浏览器 2.X