题解 | #旋转数组#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 旋转数组
     * @param n int整型 数组长度
     * @param m int整型 右移距离
     * @param a int整型vector 给定数组
     * @return int整型vector
     */

    // 找到最小公倍数
    int findMin(int a, int b){
        int n = 0;

        int max = a > b ? a : b;
        int min = a > b ? b : a;
        int cnt = max / min;
        while (1) {
            n = cnt * min;
            if(n % max == 0) break;
            ++cnt;
        }

        return n;
    }   

    vector<int> solve(int n, int m, vector<int>& a) {
        // write code here

        int tmp = 0;
        int pre = a[0];
        int idx = 0;
        m = m % a.size();
        if(m == 0) return a;
        int max = findMin(m, a.size());

        for(int i = 0; i < a.size(); i++){
            idx += m;
            tmp = a[idx % a.size()];
            a[idx % a.size()] = pre;
            pre = tmp;
            
            if(idx >= max){
                idx = idx % a.size() + 1;
                pre = a[idx];
            }
        }

        return a;
    }
};

首先需要知道如下事实：

• 最多需要交换n次
• 不能重复移动同一位置的数字
• 因为idx 可能大于size，所以使用idx % size 作为实际的索引
• (idx + (n * k)) % n = idx，如果idx每次都加m，则最终一定会形成循环，并且 idx 最早开始重复的时候一定是 idx 加上 m 和 n 的最小公倍数的时候

因此，每当idx重复的时候，将idx+1，这样就能保证每次交换的位置都是不重复的，并且上一轮的交换已经形成环，并且环中的每个位置都已经完成交换。这样n次之后，整个数组就完成了移动