例题

存在一个数组{a,b,c,d,e}，现在指定步长，让整个数组向右移动，溢出的内容补贴到左侧空出来的地方；

解法1

就直接按照题目要求描述的这样去移动…时间复杂度是O(n*k)，比O(n^2)要小一些..

解法2

使用环形替代；
例如现在要求步长k是3；
那么执行完成之后最后的结果是{c,d,e,a,b};
从结果来看..数据的移动方式为：

  1. 数据a，向后移动了三位，index（0+3）；
  2. 数据b，向后移动了三位，index（1+3）；
  3. 数据c，向前移动了两位，index（2-2）；
  4. 数据d，向前移动了两位，index（3-2）
  5. 数据e，向前移动了两位，index（4-2）

所以看明白了么….长度为5的数组，这样循环移动之后，没有发生溢出的内容的index=oldIndex+step;而发生了溢出的内容的index=oldIndex-（length-step）;
如果单纯的使用交换是达不到目的的…这时候需要使用环形替代
仍旧以{a,b,c,d,e}和步长=3来举例子：

  1. 让a到正确的位置，取代d，此时d将会从数组中被挤出来；
  2. 让d回到正确的位置，d的下标是3，属于溢出的部分，因此d的正确位置应该是3-（5-3）=1；此时b被挤了出来；
  3. 让b回到正确的位置，b的小标是1，属于不会溢出的部分，b的正确位置应当是1+3=4;此时e被挤了出来；
  4. 让e回到正确的位置，e的下标是4，属于溢出部分，因此e的正确位置是4-（5-3）=2；此时c被挤了出来；
  5. 让c回到正确的位置，c的下标是2，属于溢出部分，因此正确位置是2-（5-3）=0；正好，index=0的位置上没有元素…完成运算

环形替换的时间复杂度为O(n)，空间复杂度为O(1) 优势还是很大的…