题目
给定一个整数数组 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 <= 10^5-2^31 <= nums[i] <= 2^31 - 10 <= k <= 10^5
使用空间复杂度为 O(1) 的原地算法解决这个问题
题解
题目要求原地的方式解题，所以不能再额外创建一个长度相同的数组来进行移动。这里有一种方式，想象类似环状的数据结构进行移动处理。首先从下标为 0 的位置开始，讲元素存到 temp 临时变量中，此时移动 k 个位置，即下标为 0 的元素要移动到下标为 i=(0+k)%n 的位置上，此时将下标 i 的元素 替换为 temp 的元素 ，而 temp 中元素更新为替换前的元素，依次类推直到要移动的位置再次回到下标 0 为止。
到这里有同学要问了，这一次遍历并不能保证数组中的所有元素都遍历到，因此可能需要对下一个数字即下标为 1 的位置再开始一轮遍历。这里就有个问题，如何能得知，一共需要遍历多少次？所以这道题的主要注意力要放到推导出遍历次数这个问题上。
首先我们要思考一个问题，从下标为 0 的位置开始遍历，再次回到 0 的位置一共遍历了多少个元素？我们假设数据的长度为 n, 单次遍历个数为 p 因为最终回到起点位置，所以一定是走了整数倍的次数，我们假设走了 m 圈，如何不好理解还可以类比为从 0 为起点开始遍历，再次落在了 n 的倍数的点上。因此一共遍历的长度为 l=mn 也可以表示为 l=kp , 因此有 mn=kp。进而我们可以得到 l 是 n 和 k 的最小公倍数 lcm(n,k), 最终我们得知单次遍历个数 p=lcm(n,k)/k 。
然后，我们可以推倒出共需要遍历次数为 n/p, 即 n/(lcm(n,k)/k) -> nk/lcm(n,k) -> gcd(n,k)。
最后推导出数组长度为 n 的数组，向右轮转 k 个位置，共需遍历次数为 n 和 k 的最大公约数。下面给出此题的 go 题解。
func rotate(nums []int, k int) {
count := gcd(len(nums), k)
for start := 0; start < count; start++ {
temp, cur := nums[start], start
for ok := true; ok; ok = cur != start {
next := (cur + k) % len(nums)
nums[next], cur, temp = temp, next, nums[next]
}
}
}
func gcd(a, b int) int {
for b != 0 {
a, b = b, a%b
}
return int(math.Abs(float64(a)))
}
...