Share my solution , o(1) space , o(n) time, c++


  • 0
    Z
    class Solution {
    public:
        void rotate(vector<int>& nums, int k) {
            int sz = nums.size();
            if(sz == 0) return ;
            int d = gcd(k, sz);
            
            for(int i=0; i<d; i++) {
                int tmp = nums[i];
                int idx = i+k;
                idx %= sz;
                while(idx!=i) {
                    swap(tmp, nums[idx]);
                    idx+=k;
                    idx%=sz;
                }
                swap(tmp, nums[idx]);
            }
        }
        int gcd(int a, int b) {
            if(a%b == 0) return b;
            else return gcd(b, a%b);
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.