从0开始的秋招刷题路，记录下所刷每道题的题解，帮助自己回顾总结

189. 轮转数组

给定一个整数数组 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 <= 10510^5105
−231-2^{31}−231 <= nums[i] <= 231−12^{31} - 1231−1
0 <= k <= 10510^5105

进阶：
尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。
你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？

思路
从nums[0]开始，放到该数的新位置(0 + k)，然后再寻找该位置值的新位置，直至回到0时结束。 但是该方法不能保证遍历完所有的位置，如 7 位的数组后移3个位置只需遍历一遍，而 6 位的数组后移4个位置需要遍历两遍（再从i = 1开始）。 可以发现这个遍历的次数就是数组长度和k的最大公约数。

代码

public void rotate(int[] nums, int k) {int len = nums.length;for (int i = 0;i < gcd(k, len);i++){int idx = (k + i) % len, num = nums[i];while (idx != i){int item = nums[idx];nums[idx] = num;idx = (idx + k) % len;num = item;}nums[i] = num;}
}private int gcd(int a, int b) {return a % b == 0 ? b : gcd(b % a, a);
}