【出自TX面试题】
难度系数：★★★☆☆ 被考察系数：★★★☆☆
题目描述：
把一个含有N个元素的数组循环右移K（K是正数）位，要求时间复杂度为O（N），且只允许使用两个附加变量。
分析与解答：
由于有空间复杂度的要求，因此，只能在原数组中就地进行右移。
方法一：蛮力法
蛮力法是最简单的方法，题目中需要将数组元素循环右移K位，只需要每次将数组中的元素右移一位，循环K次即可。例如，假设原数组为abcd1234，那么，按照此种方式，具体移动过程如下所示：abcd1234→4abcd123→34abcd12→234abcd1→1234abcd。
此种方法也很容易写出代码。示例代码如下：
程序的运行结果如下：
5 6 7 8 1 2 3 4
以上方法虽然可以实现数组的循环右移，但是由于每移动一次，其时间复杂度就为O（N），所以，移动K次，其总的时间复杂度为O（K*N），0＜K＜N，与题目要求的O（N）不符合，需要继续往下探索。
对于上述代码需要考虑到，K不一定小于N，有可能等于N，也有可能大于N。当K＞N时，右移K-N之后的数组序列跟右移K位的结果一样，所以，当K＞N时，右移K位与右移K′（其中K′=K%N）位等价，根据以上分析，相对完备的代码如下：
算法性能分析：
上例中，算法的时间复杂度为O（N2），与K值无关，但时间复杂度仍然太高，是否还有其他更好的方法呢？
仔细分析上面的方法，不难发现，上述方法的移动采取的是一步一步移动的方式，可是问题是，题目中已经告知了需要移动的位数为K，为什么不能一步到位呢？
方法二：空间换时间法(www.xing528.com)
通常情况下，以空间换时间往往能够降低时间复杂度，本题也不例外。
首先定义一个辅助数组T，把数组A的第N-K+1到N位数组中的元素存储到辅助数组T中，再把数组A中的第1到N-K位数组元素存储到辅助数组T中，然后将数组T中的元素复制回数组A，这样就完成了数组的循环右移，此时的时间复杂度为O（N）。
虽然时间复杂度满足要求，但是空间复杂度却提高了。由于需要创建一个新的数组，所以，此时的空间复杂度为O（N），鉴于此，还可以对此方法继续优化。
方法三：翻转法
把数组看成由两段组成的，记为XY。左旋转相当于要把数组XY变成YX。先在数组上定义一种翻转的操作，就是翻转数组中数字的先后顺序。把X翻转后记为XT。显然有（XT）T=X。
首先对X和Y两段分别进行翻转操作，这样就能得到XTYT。接着再对XTYT进行翻转操作，得到（XTYT）T=（YT）T（XT）T=YX。正好是期待的结果。
回到原来的题目。要做的仅仅是把数组分成两段，再定义一个翻转子数组的函数，按照前面的步骤翻转三次就行了。时间复杂度和空间复杂度都合乎要求。
对于数组序列A={123456}，如何实现对其循环右移2位的功能呢？将数组A分成两个部分：A[0～N-K-1]和A[N-K～N-1]，将这两个部分分别翻转，然后放在一起再翻转（反序）。具体如下：
（1）翻转1234：123456---＞432156
（2）翻转56：432156---＞432165
（3）翻转432165：432165---＞561234
示例代码如下：
算法性能分析：
此时的时间复杂度为O（N）。主要是完成翻转（逆序）操作，并且只用了一个辅助空间。
引申：上述问题中K不一定为正整数，有可能为负整数。当K为负整数的时候，右移K位，可以理解为左移（-K）位，所以，此时可以将其转换为能够求解的情况。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
