Accepted C++ Solution with O(n) time and O(1) space


  • 0
    J
    class Solution {
        int gcd(int m, int n) // put m and n such that m >= n
        {
            int l;
            while (m && n)
            {
                l = n;
                n = m%n;
                m = l;
            }
            return m;
        }
    
        void rotate3(vector<int>& nums, int k)
        {
            int size = nums.size();
            int next, tmp0, tmp1;
            int n = gcd(size, k);
            for (int i = 0; i < n; i++)
            {
                tmp0 = nums[i];
                next = (k+i)%size;
                while(next != i)
                {
                    tmp1 = nums[next];
                    nums[next] = tmp0;
                    next = (next+k) % size;
                    tmp0 = tmp1;
                }
                nums[i] = tmp0;
            }
        }
    
    public:
        void rotate(vector<int>& nums, int k)
        {
            if (nums.size() < 2) return;
            k = k % nums.size();
            if (k == 0) return;
            rotate3(nums, k);
        }
    };

Log in to reply
 

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