https://leetcode.cn/problems/rotate-array

循环轮换

时间要O(n)，空间要O(1),那就要让元素在原数组上原地交换，不能再去创建数组，而且移动k次不能是循环k次，每次移动一格，而是让元素直接换到+k的位置。 要实现原地交换会出现一个问题，就是数据会被覆盖掉。可以把即将被覆盖的数据存进临时变量。但是这个数据存下来以后必须立刻存回数组，如果全都想存进临时变量，等到之后再处理，那么空间复杂度就不是O(1)而是O(n)了。 想要立即存回数组，只能让这个元素继续和后面的元素交换。一直这样交换下去。最终一定会回到一开始出发的那个位置（每次走k步，而数组总长为n，那么走n和k的最小公倍数一定回来）。但是会发现，这个交换的情况会和n和k的性质有关，有的时候这样走一轮，全部元素都走到了，有的时候这样只能在固定的几个元素里交换。下面做一下数学上的推理：

刚才已经确定了：每次走k步，而数组总长为n，那么走n和k的最小公倍数步一定回来，也就是走了$lcm(n,k)$步。k步是一个元素，那么总共交换到了$\frac{lcm(n,k)}{k}$个元素，很明显如果n和k不互质，交换到的元素肯定不是n。如果让出发位置改变一下，就可以遍历到其他的元素，这样多走几轮就可以覆盖全部n个元素。走的轮次数量为

$$\frac{n}{\frac{lcm(n,k)}{k}}=\frac{nk}{lcm(n,k)}=gcd(n,k)$$

所以，我只要从下标0~gcd(n,k)-1开始轮换元素，就可以完成整个过程。

实现

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        int round_cnt = gcd(n,k);
        for(int i = 0; i<round_cnt;i++){
            //i为起点
            int p =i;
            int tmp = nums[p];
            do{
                swap(tmp,nums[(p+k)%n]);
                p = (p+k)%n;
            }while(p!=i);
        }
    }
};

每一轮轮换，i被定义为起始下标，用p标记当前所在下标，初始为i。tmp用于暂存被取出数组的元素，通过swap和新的元素进行轮换，swap让前面的元素换进新的位置，同时把新位置的元素取回到tmp里。交换完了以后让p向前走k步。用do-while是因为判断条件的p!=i会在一开始p初值的时候就不成立，先走一次把p改掉。