n个元素的数组向左循环移动i个位置

算法的完美

时间:2012-03-19 / 分类:学习园地,网络文摘 / 浏览:1797 / 0个评论 发表评论

考虑一个问题:将一个具有n个元素的数组向左循环移动i个位置。有许多应用程序会调用这个问题的算法,例如在文本编辑器中移动行的操作,磁盘整理时交换两个不同大小的相邻内存块等。所以,这个问题的算法要求有较高的时间和空间性能。

可以通过下面的方法解决这个问题:先将数组中的前i个元素存放在一个临时数组中,再将余下的n-i个元素左移i个位置,最后将前i个元素从临时数组复制回原数组中后面的位置。但是这个算法使用了i个额外的存储单元,使得空间性能降低。

还有一个方法可以解决这个问题:先设计一个函数将数组向左循环移动一个位置,然后再调用该算法i次,显然,这个算法的时间性能不好。

要在有限的资源中解决这个问题,似乎很困难。现在我们换一个角度看这个问题:将这个问题看作是把数组ab转换成数组ba(a代表数组的前i个元素,b代表数组中余下的n-i个元素),先将a逆置得到arb,再将b逆置得到arbr,最后将整个arbr逆置得到(arbr)r=ba。设Reverse函数执行将数组元素逆置的操作,对abcdefgh向左循环移动3个位置的过程如下:

Reverse(0, i-1); //得到cbadefgh

Reverse(i, n-1); //得到cbahgfed

Reverse(0, n-1); //得到defghabc

  其原理可以用一个简单的游戏来理解:将两手的掌心对着自己,左手在右手上面,可以实现将一个具有10 个元素的数组向左循环移动5位,如图1-12所示。

n个元素的数组向左循环移动i个位置

该算法在时间和空间上都很有效,并且是这么简短和简单,想出错都很难。Brian Kernighan在Software Tools in Pascal中使用了这个算法在文本编辑器中移动各行。     作为一个规律,一个好的算法是反复努力和重新修正的结果,即使足够幸运地得到了一个貌似完美的算法思想,我们也应该尝试着改进它。

上一篇:selenium控制浏览器


下一篇:两个有序数组中的中位数以及求第k个最小数的值