My c++ recursion solution space O(n)


  • 0
    T
    class Solution {
    public:
    
        void rotate(vector<int>& nums, int k) {
            
            int n = nums.size();
            if( n <= 1 || ( k %= n ) == 0)
                return;
            
            _rotate(nums, 0 , n, k);
        }
    
    private:
    
        void swap(vector<int>& nums, int i, int j)
        {
            int x   = nums[i];
            nums[i] = nums[j];
            nums[j] = x;
        }
    
        void _rotate(vector<int>& nums, int pos, int n, int k)
        {
            if( n <= 1 || k == 0 || n == k)
                return ;
            
            if( k <= n /2 )
            {
                for( int i = 0; i < k; ++i)
                    swap( nums, i + pos, i + pos + n - k);
                
                _rotate(nums, pos + k, n - k, k );
            }
            else
            {
                for( int i = 0; i < n - k; ++i)
                    swap( nums, i + pos, i + pos + k);
                
                _rotate(nums, pos , k, 2*k - n);
            }
        }
    };

  • 0

    Recursive solutions are never O(1) space.


  • 0
    T

    You are right, it should be O(n)


Log in to reply
 

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