189. Rotate Array

第三种方法太复杂了，只会第四种

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        k %= nums.size();
        reverse(nums, 0, nums.size() - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.size() - 1); 
    }
private:
    void reverse(vector<int>& nums, int start, int end)
    {
        while(start < end)
            swap(nums[start++], nums[end--]);
    }
};

1 2	an=bk b走的步长为k，所以走了一圈后b*k是n的倍数，所以需要求a

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        if((k %= n) == 0)
            return;
        int count = gcd(n, k);
        for(int i = 0; i < count; ++i)
        {
            int prev = nums[i];
            int cur = i;
            do
            {
                int next = (cur + k) % n;
                swap(prev, nums[next]);
                cur = next;
            }while(cur != i);
        }
    }
};