交换两个数据块位置(数组的连续移位)

连续的数据,如 abcdefg , 经过多次循环移位后,(如 abcdefg 经一次循环移位后变为 bcdefga ),该数据会变为什么。

我们知道数组的移位是O(n),很耗时间,如果连续移动 m 次的话时间消耗会很大。最近在读《编程珠玑》, 上边提供了两种算法。第一种称之为 “杂技算法”,即给定一些临时空间(设为可存放k个数据,需连续移动m次),先将前 k 个数据放入里面,之后将第 m+1 到第 m+k 个数据移入第 1 个到第 k 个中,其后依次移入其所在位置。(本文章并不想详细说此方法)。

第二种方法则比较巧妙,使我想起了暑假集训时做到的一道题目。那道题目和本题很相似,不过是要做多次这种连续移位,更加复杂。但其解决方法的思想和第二种方法思想一致。若总共有 n 个数据,要连续移动 m 次,算法如下:

  • Reserve(0, m-1)
  • Reserve(m, n-1)
  • Reserve(0, n-1)

abcdefg , 第一步翻转后变为 cbadefg , 第二步后变为 cbagfed , 第三步后变为 defgabc。 即为答案,十分巧妙!

暑假那题因为需要多次进行连续移位,所以用到了 Splay树。还有巨巨们用了 rope(块状链表)。 也是我第一次听说这种数据结构。不过 Splay树效率更高些。

❤采之欲遗谁,所思在远道。❤
0%