THREE solutions O(N) time/O(1) space in c++


  • 0
    S

    solution1: double reverse
    solution2: circular rotation using largest common divider
    solution3: recursive

    class Solution {
    void reverse(vector<int>& nums, int first, int last) {
    while (first < last) {
    swap(nums[first++], nums[last--]);
    }
    }

        int largestCommonDivider(int x, int y) {
            if (x < y) swap(x, y);  // ensure x >= 1;
            while (x % y != 0) {
                x %= y;
                swap(x, y);
            }
            return y;
        }
        
    public:
        void rotate(vector<int>& nums, int k) {
            int n = nums.size();
            if (n < 2) return;
            k %= n;
            if (k == 0) return;
            
            rotate3(nums, 0, n - k, k);
        }
    
        void rotate1(vector<int>& nums, int k) {
            reverse(nums, 0, nums.size() - k - 1);
            reverse(nums, nums.size() - k, nums.size() - 1);
            reverse(nums, 0, nums.size() - 1);
        }
        
        void rotate2(vector<int>& nums, int k) {
            int n = nums.size();
            int commonDivider = largestCommonDivider(n, k);
            for (int start = 0; start < commonDivider; ++start) {
                int valueToMove = nums[start];
                for (int i = 1; i <= n/commonDivider; ++i) {
                    int targetPos = (i*k + start) % n;
                    swap(valueToMove, nums[targetPos]);
                }
            }
        }
        
        void rotate3(vector<int>& nums, int start, int k1, int k2) {
            while (true) {
                int kMin = min(k1, k2);
                int kMax = max(k1, k2);
                for (int i = 0; i < kMin; ++i) {
                    swap(nums[start + i], nums[start + i + kMax]);
                }
                if (k1 < k2) {
                    k2 -= k1;
                } else if (k1 > k2) {
                    start += kMin;
                    k1 = k1 - k2;
                } else {
                    break;
                }
            }
        }
    };

Log in to reply
 

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