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

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

设将 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
关于作者:
一个从石头坑掉到泥坑里的攻城狮。
尊敬的汽车发表我的评论  请填写正确的 个人信息
取消评论
表情 加粗 斜体 签到
(5)个小伙伴在吐槽
  1. Uk Pharmacies That Deliver To Usa Acquisto Levitra Farmaci Originali Viagra Store In Canada viagra How To Buy Ed Drugs From Canada Cialis Oder Generika Diarrhea Amoxicillin 500 Mg
    Ellquiept2019-05-31 21:35 回复 Windows 10 | Chrome 68.0.3440.75
  2. 好文章!666,学习了
    888pv2019-05-05 21:35 回复 Windows 7 | 未知浏览器
  3. 好文章!666,学习了
    okkeep2019-05-05 21:17 回复 Windows 7 | 未知浏览器
  4. 博主的代码高亮用的是插件吗?
    独特的睫毛膏2018-08-24 21:26 回复 Windows 10 | Chrome 68.0.3440.75
    • TOMORROW
      对的,pure highlight
      TOMORROW2018-08-24 23:43 回复 Windows 10 | 搜狗浏览器 2.X