189. 旋转数组

发表于 分类于 ， 阅读次数： 本文字数： 98 阅读时长 ≈ 1 分钟

#题意

使用O(n)时间和O(1)空间旋转数组

#思路

数学题, GCD

#感想

下次遇到这种题画个图会更好理解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n=nums.size();
        if(!n || n == 1)return;
        if(!(k %= n))return;
        for(int c=0, _gcd=gcd(n,k); c<_gcd; c++){
            int tmp = nums[c];
            int x=c,_x;
            while((_x=(x-k+n)%n)!=c){
                nums[x]=nums[_x];
                x=_x;
            }
            nums[x]=tmp;
        }
    }
};