平移数组（Rotate Vector）

algorithm

(Banner图片来自一喜欢摄影的同学：心碎乌托邦)

问题

Rotate a one-dimensional vector of n elements left by i positions. For instance, with n = 8 and i = 3, the vector abcdefg is rotated to deftabc.

Naive idea

  1. 另外声明一个数组存储前i个元素，然后把后面的元素左移i位，最后再把数组里面 的i个元素复制到原数组的最右边的i个位置。显然这种方法是空间复杂度是O(i)，时间 复杂度O(n).
  2. 另t=x[0],然后move x[i] to x[0], x[2i] to x[i]，依次类推，然后再 把t放到最后的位置；然后是x[1]，最后一直到x[i-1]。空间复杂度O(1)，时间 复杂度O(n).

    Aha!

首先，show the code: 

1
2
3
reverse(0, i-1);    /* cbadefgh */
reverse(i, n-1);    /* cbahgfed */
reverse(0, n-1);    /* defghcba */

这算法的过程的有点神奇，过程比较清楚，分为三步：

  1. 反转前i个元素;
  2. 反转后面n-i个元素;
  3. 反转所有的n个元素。

虽然结果正确，但难免没有说服力，先面就证明一下。

  1. 对于0 <= x < i的元素，第一步反转以后,x的位置为x', 因为x'和x关于 i/2对称，所以

    x' = i-x

  2. 对于0 <= y < i的元素，第二步反转以后,y的位置为y', 因为y'和y关于 (n-1+i)/2对称，所以

    y' = n-1+i-y

  3. 对于x，平移以后最终的位置是x => n-1+x-i。 第三步反转后，x'的位置为:

    x' => n-1 - x' = n-1+x-i

  4. 对于y，平移以后最终的位置是y => y-i。 第三步反转后，y'的位置为:

    y' => n-1 - y' = y-i

证明结束。

同时可以引出一个公式： 该公式推广：