给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

示例 2:

输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

提示：

  • 1 <= nums.length <= 105
  • -231 <= nums[i] <= 231 - 1
  • 0 <= k <= 105

题意挺好理解，就是将一个数组循环右移嘛。如果能够使用一个额外的数组，那将是非常容易，将数据拷贝一份，然后依次拷贝到偏移下标的地方，但是如果要求O(1)的空间复杂度呢？也是不难想起来，比如示例一，从下标0开始，依次将下标0的元素挪到下标3，即1挪到4的位置，以此类推，4挪到7的位置……，但是点子易得，方案难想，因为里面有许多细节需要确定。比如就这样挪动下去，截至条件是啥呢？一个很自然的想法是对挪动次数计数，截止条件就是计数值等于数组长度，我当时就是这么想得，可是这不是全部的真相。比如举个简单的例子，数组为[1,2,3,4]，k为2，但是挪动的过程会发生循环移动的情况，也就是下标0挪到下标2，下标2又挪到下标0，接着还是这个过程，最后循环截至，下标1和下表3根本没动，这显然不对。

那真正的全部真相是什么样的呢？我也是看了答案才知道。原来这种挪动，挪到最后会回到起始点，到了起始点之后，开启第二轮挪动，第二轮挪动的起始点是第一轮的下一个位置，这种挪动会持续多轮才能完成。我看了答案，不禁大呼人比人真是气死人，这脑子咋长得？接着我就有了三个疑问，一是为什么这种挪动会回到起点，二是多轮之间会不会有交集？三是一共要进行多少轮？

首先第一个问题，为什么会回到起点？假设数组长度为n，每一步为k，要回到起点也就是要走整数个n的长度，也就是k走的够多，最终肯定会有一个数等于n的倍数，第一个遇到的就是最小公倍数嘛，为了方便将最小公倍数记为$LCM(n, k)$。

第二个问题，轮与轮之间难道没有交集吗？这个问题我们不妨反过来想，假如两轮之间有交集，这意味着一轮还没结束，因为这个交集元素两轮都可达，如果是这样，又称不上两轮了，因此不同轮次之间没有交集。

第三个问题，需要多少轮？一轮总共走了$LCM(n, k)$的距离，步长为k，那一轮应该是$step = LCM(n, k) / k$步，即挪动了这么多元素，因此需要$n / step = n*k / LCM(n, k) = 最大公约数 = GCD(n, k)$轮。相信那些和我一样将代数知识早已还给老师的人看到这里已是一脸懵逼，你不是一个人，我们一起复习下。

对于两个整数n和k，它们的最小公倍数$LCM(n, k)$和最大公约数$GCD(n, k)$有如下关系：

$$LCM(n, k) * GCD(n, k) = n * k$$

学有余力的同学可以看看下面的证明，来自chatgbt。

假设有两个整数 n 和 k，它们的最大公约数为 d（即 GCD(n, k) = d）。那么我们可以表示 n 和 k 如下：

n = d * a
k = d * b

在这里，a 和 b 是整数，它们分别表示 n 和 k 相对于它们的最大公约数 d 的倍数。这个分解的关键是，a 和 b 是互质的，即它们没有除 1 以外的共同因子。

那么 n 和 k 的最小公倍数可以表示为：

LCM(n, k) = LCM(d * a, d * b)

由于 a 和 b 互质，它们的最小公倍数为 1，因此最小公倍数可以简化为：

LCM(n, k) = d * LCM(a, b)

而 LCM(a, b) 就是 a 和 b 的乘积，即 a * b。

所以，最小公倍数和最大公约数之间的关系为：

LCM(n, k) = d * (a * b) = d * (n / d * k / d) = (n * k) / d = (n * k) / GCD(n, k)

即LCM(n, k) * GCD(n, k) = n * k

解答了这三个问题可以得出两点结论：

  1. 需要挪动多轮，即$GCD(n, k)$轮
  2. 每一轮的截至条件是到达起点

由此，我们写出代码。

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k = k % n;
        int count = gcd(n, k);
        for (int start = 0; start < count; start++) {
            int si = start;
            int source = nums[si];
            do {
                int ti = (si + k) % n;
                int target = nums[ti];
                nums[ti] = source;
                source = target;
                si = ti;
            } while (si != start);
        }
    }

    private int gcd(int x, int y) {
        return y > 0 ? gcd(y, x % y) : x;
    }
}