My C++ 24ms O(1) space solution


  • 0
    E
    class Solution {
    public:
        void rotate(vector<int>& nums, int k) {
            int n = nums.size();
            k = k % n;
            rotateBlock(nums, 0, n-k, n-k, k);
        }
        void rotateBlock(vector<int>& nums, int leftBegin, int leftSize, int rightBegin, int rightSize) {
            if(leftSize == 0 || rightSize == 0) {
                return;
            }
            if(leftSize > rightSize) {
                swapBlock(nums, leftBegin, rightBegin, rightSize);
                rotateBlock(nums, leftBegin+rightSize, leftSize-rightSize, rightBegin, rightSize);
            } else {
                swapBlock(nums, leftBegin, rightBegin, leftSize);
                rotateBlock(nums, rightBegin, leftSize, rightBegin+leftSize, rightSize-leftSize);
            }
        }
        void swapBlock(vector<int>& nums, int swapFrom, int swapTo, int blockSize) {
            int n = nums.size();
            if( (swapFrom + blockSize) > n || (swapTo + blockSize) > n ) {
                return;
            }
            for(int i = 0; i < blockSize; i++) {
                swap(nums[swapFrom+i], nums[swapTo+i]);
            }
        }
    };

Log in to reply
 

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