Is this solution O(n) time and O(1) space?


  • 0
    C
    public int gcd(int n, int k) {
    	return n%k==0?k:gcd(k, n%k);
    }
    public void rotate(int[] nums, int k) {
    	int n=nums.length;
    	k%=n;
    	if (k==0) return;
    	int g=gcd(n, k);
    	for (int i=0;i<g;i++) {
    		int j=i, l=(i+n-k)%n, tmp=nums[i];
    		while (l!=i) {
    			nums[j]=nums[l];
    			j=l;l=(l+n-k)%n;
    		}
    		nums[j]=tmp;
    	}
    }

Log in to reply
 

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