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

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

题目描述

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

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

思路1:

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

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

假设从0出发，回到0的时候一共走了$a$圈，经历了$b$个数字，则可以得到恒等式 $a\ast n=k\ast b$，同时，不难发现，从任意一个点出发，走n和k的最小公倍数的倍数圈就可以回到原点，所以最小值就取 $lcm(n,k)$，即$a\ast n=lcm(n,k)$，根据恒等式，$k\ast b=a\ast 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\ast k}{lcm(n,k)}$，由于$n\ast k=gcd(n,k)\ast 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]);
        }
    }
};