Simple c++ solution with detail explain and O(1) extra space


  • 12
    Q
     /**
     * this solution is so-called three times rotate method
     * because (X^TY^T)^T = YX, so we can perform rotate operation three times to get the result
     * obviously, the algorithm consumes O(1) space and O(n) time
     **/
    class Solution {
    public:
        void rotate(int nums[], int n, int k) {
            k %= n; // if k > n then the final result is the same as k%n
            reverseArray(nums, n-k, n-1);
            reverseArray(nums, 0, n-k-1);
            reverseArray(nums, 0, n-1);
            
        }
        /**
         * rotate the array nums from start to end
        **/
        void reverseArray(int nums[],int start, int end){
            while(start < end){
                int temp = nums[start];
                nums[start++] = nums[end];
                nums[end--] = temp;
                // or you can simply code as "std::swap(nums[start++], nums[end--])" to replace above three lines
            }
        }
    };

  • 0
    L

    Though there's one more elegant solution. I still like your way. It's straight and simple enough for normal people like me to understand.


  • 0
    C

    Nice explanation, I like the name so-called three rotation method, and it takes exactly n operations, should be best performance algo from my understanding.


Log in to reply
 

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