One solution without additional space and with O(n) time complexity


  • 0
    Y
    /*
    M(T)N(T) = (NM)(T)
    NM = (M(T)N(T))(T)
    */
    
    /*
    ** Example a[6]={1,2,3,4,5,6},n=6,k=2
    ** step 1: {4,3,2,1,5,6} -> M(T)
    ** step 2: {4,3,2,1,6,5} -> N(T)
    ** step 3: {5,6,1,2,3,4} -> (M(T)N(T))(T)
    */
    
    void swap(int* a, int* b)
    {
        *a = *a ^ *b;
        *b = *a ^ *b;
        *a = *a ^ *b;
    }
    
    void rotate(int nums[], int n, int k)
    {
        int i=0;
        if(k <= 0)
            return;
        if(k >= n)
            k = k % n;
        for(i = 0 ; i< (n-k)/2 ; ++i)
        {
            swap(&nums[i], &nums[n-k-i-1]);
        }
    
        for(i = n-k ; i < n-k+k/2 ; ++i)
        {
            swap(&nums[i], &nums[2*n-k-1-i]);
        }
    
        for(i = 0 ; i < n/2 ; ++i)
        {
            swap(&nums[i],&nums[n-i-1]);
        }
    }

Log in to reply
 

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