C++solution, O(n)time,O(1)space


  • 0
    A
    class Solution {
    public:
        void rotate(int nums[], int n, int k) {
            
                int group = gcd( n, k );    // number of cycling chain
        	int elemInSub = n / group;   // number of elements in every chain
        	for( int j = group-1; j >= 0; j-- )
        	{
        		int tmp = nums[ (j+(elemInSub-1)*k)%n ];
        		int i;
        		for( i = elemInSub-1; i>0; i-- )
        			nums[ (j+i*k)%n ] = nums[ (j+(i-1)*k)%n ];
        		nums[ j ] = tmp;
        	}
        }
        int gcd(int m, int n)
        {
        	if( n == 0 )
        		return m;
        	return gcd( n, m % n );
        }
    };

Log in to reply
 

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