A 1ms in-place Java solution with explanation


  • 0
    L
    1. The basic idea to do the rotation in place is by swapping elements in the way like
      tmp = a a=b b=tmp
      But in this problem, elements are not swapped in pairs, so we need to store the current element in one place to write it into next place. Therefore, we need to write code like following
      tmp1 = a a=tmp tmp=tmp1

    2. How to calculate the next place to swap? And how to iterate the array? The answer is modulo, as you just come up with. But to use modulo, we still should pay attention to some properties.
      a) If the gcd of the array length n and k is 1, then we can simply iterate n times, with each time adding the index by k and modulo by n, finally we will iterate the entire array.
      b) If the gcd of n and k is larger than 1, say 2 and 4 or 4 and 6, then we will have several groups of indices which will iteration within themselves forever. For example, {0,2},{1,3} are two groups, {0,2,4},{1,3,5} are two groups. Therefore, after one group is iterated, we must change the start point to next group to ensure that the entire array can be iterated. To justify whether the iteration of a groups is completed, we can leverage lcm.
      Actually we will find that situation a) is included in situation b), therefore we can handle these two situations at the same time.

    Following is my code.

    public class Solution {
        public void rotate(int[] nums, int k) {
            if(nums.length<=k) k=k%nums.length;
            if(k==0) return;
            
            int gcd = GCD(nums.length,k);
            int lcm = nums.length*k/gcd;
            int start = 0;
            for(int i=0;i<nums.length;){
                int temp = nums[start];
                int index;
                for(index = start++;index<lcm;index+=k){
                    int temp1 = nums[index%nums.length];
                    nums[index%nums.length] = temp;   
                    temp = temp1;
                    i++;
                }
                nums[index%nums.length] = temp;
            }
        }
        
        private int GCD(int num1, int num2){
            if(num1%num2==0) return num2;
            else{
                return GCD(num2, num1%num2);
            }
        }
    }
    

Log in to reply
 

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