「力扣面试经典150题」189. 轮转数组

题目描述

给定长度为$n$的数组$ar$，将数组中的元素向右轮转$k$个位置，其中$k$是非负数

要求使用空间复杂度为$O(1)$的原地算法解决

思路1:

比较粗糙一点的想法是，选定某个位置，从当前位置开始往后找到右边第k个位置，进行赋值，继续找下一个，知道回到最初选定的位置

但是很显然，有的时候不会只走一圈就全部轮转成功，我们需要考虑一下最少需要选几个数字可以覆盖整个数组。

假设从0出发，回到0的时候一共走了$a$圈，经历了$b$个数字，则可以得到恒等式 $a*n=k*b$，同时，不难发现，从任意一个点出发，走n和k的最小公倍数的倍数圈就可以回到原点，所以最小值就取 $lcm(n,k)$，即$a*n=lcm(n,k)$，根据恒等式，$k*b = a*n=lcm(n, k)$，可以得到 $b=\frac{lcm(n,k)}{k}$，每走一圈可以遍历到b个数字，想遍历$n$个数字，则只需要取前num个，$num = \frac{n}{b} = \frac{n}{\frac{lcm(n, k)}{k}} = \frac{n * k}{lcm(n, k)}$，由于$n*k=gcd(n,k)*lcm(n, k)$，所以$num = gcd(n, k)$

class Solution {
public:
    int gcd(int x, int y){
        if(y == 0)return x;
        return gcd(y, x % y);
    }
    void rotate(vector<int>& num, int k) {
        int n = num.size();
        k %= n;
        if(k == 0)return;
        for(int p = 0; p < gcd(n, k); ++p){
            int u = p, x = num[u], y = 0;
            do{
                int v = (u + k) % n;
                y = num[v];
                num[v] = x;
                x = y;
                u = v;
            }while(u != p);
        }
    
    }
};

思路2:

三次翻转数组

首先把整个数组反转一遍，再将前$k$个数反转一遍，再将后$n-k$个数反转一遍即可得到答案

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k %= n;
        if(k == 0)return;
        reverse(nums.begin(), nums.end());
        for(int l = 0, r = k - 1; l < r; ++l, --r){
            swap(nums[l], nums[r]);
        }
        for(int l = k, r = n - 1; l < r; ++l, --r){
            swap(nums[l], nums[r]);
        }
    }
};