这道题题面很简单：给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

这道题另辟空间的做法很简单，就不赘述了。本篇文章记录的是官方题解中介绍的一种就地方法。

这种方法描述的基本操作是很符合基本直觉的：比如以下标 1 举例，把小标 1 的数移到下标 1 + k 处，再把原先下标 1 + k 中的数移到下标 1 + k + k 中，……，以此反复。但是由此带来了一个当时百思不得其解的问题：

1. 以上反复就地轮转的操作会破坏原先存储的内容么，会不会有被重复交换的区域？

代码

先直接上代码，结合说明实际的算法。如代码清单 1 所示，实际的做法是：从第一个数开始轮转，它最终会回到第一个数；再从第二个数开始轮转，它最终也会回到第二个数；……；以此反复，直到记录到每个位置都被轮转过了，就结束。

以上的方法非常让我费劲，由此带来另外两个问题：

2. 由解法可知，非但不会有 1 中担心的重复轮换的问题，而且从哪处开始轮换就会重新回到轮换的位置！

3. 一整轮轮换可能不会把所有数都轮换过，为什么从下一个紧邻的数开始轮换，下一个数难道不会在上一轮中已经被轮换过了么？！

解释

当时翻遍了力扣下的题解，没有能清楚“说服”我以上问题的，不过评论里有提到和 Polya 计数 相关。我准备从这处入手，发现 Polya 计数还没看完，看前置基础知识的时候，已经能解决问题 1 和 2 了。

我们画一下四个数情况下的所有轮换情况，只有四种轮换情况：往后移动 0、1、2、3 个位置。比如往后移动 2 位的情况是：1 移到 3，3 移到 1；2 移到 4，4 移到 2。

从图 1 至 图 4 中，我们可以看到所有的情况都是按环的形式呈现的。其实轮转就是一种置换，某个元素会从原先的位置置换出去，原先的位置还会置换得到新的元素。可以理解成每个位置（或者每个元素）的出度和入度有且仅能是 1。那么呈现的形式只能是环。

因为呈现形式是环，出度入度都是 1，那么能很好的解释问题 1 和 2：是环所以从哪里开始会从哪里结束；一轮轮转中不会重复轮转，否则会破坏环的结构。

接下来要证明问题 3。问题 3 换个更个例的问题是，为什么相邻的数在前一个环中，就代表全部数已经都轮转完成了；更普遍的问题是，整个数组会有多少个环，各个环中的元素会是什么。

我们从更普遍的问题入手。以位置 1 举例，\(1+kx\ mod\ n\) 是以 1 为代表的环。取余运算，让问题变得抽象难以处理，所以我们“化环为直”，直接看 1 往后偏移 \(r\) 个位置，谁和它在一个环里，即求 \(r\) 满足：

\(1+kx\ mod\ n = 1 + r\)

以上式子可以变型为：

\(1+kx=ny+1+r\)

最终化简成：

\(kx-ny=r\)

这就是 裴蜀定理。要想求解成立，即方程有解，\(r\) 只能满足：

\(r\ |\ gcd(k,n)\)

至此问题就解决了，以 1 举例，环中有：

\(\{1,1+gcd(k,n),1+2*gcd(k,n),\cdots\}\)

以 2 为首的环同理。更特例的举例，\(gcd(k,n)=1\)，一轮轮换就全部遍历到；更普遍的答案，总共有\(gcd(k,n)\)个环。

之前代码清单 1 中是按计数的方法，确定每个元素是否都轮转完成。现在我们额外知道会有多少个环了，可以对代码进行改造一下。