Give a new kind of solution: using gcd and DFS, time:O(n), space:O(1)


  • 1
    X

    May be this is a new solution using GCD and DFS

    
    class Solution {
    public:
    	void dfs(int ni, int k, vector<int>& nums){
    		int ln=nums.size();
    		int newN=(ni+k)%ln;
    		int tmp=nums[ni];
    		nums[ni]=INT_MIN;
    		if(nums[newN]==INT_MIN){
    			nums[newN]=tmp;
    			return;
    		}else{
    			dfs(newN, k, nums);
    			nums[newN]=tmp;
    		}
    	}
    	int gcd(int a, int b){
    		return b==0?a:gcd(b, a%b);
    	}
    			  
        void rotate(vector<int>& nums, int k) {
    		if(k==0) return;
    		int ln=nums.size();
    		k=k%ln;
    		int g=ln/gcd(ln,k);
    		
    		for(int i=0;i<ln/g;i++){
    			dfs(i, k, nums);
    		}
        }
    };

Log in to reply
 

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