My three way to solve this problem, the first way is interesting(JAVA)


  • 61

    Method 1: ( Interesting way, O(n) time cost, O(1) space cost)

    public class Solution {
        public void rotate(int[] nums, int k) {
            if(nums.length <= 1){
                return;
            }
            //step each time to move
            int step = k % nums.length;
            //find GCD between nums length and step
            int gcd = findGcd(nums.length, step);
            int position, count;
            
            //gcd path to finish movie
            for(int i = 0; i < gcd; i++){
                //beginning position of each path
                position = i;
                //count is the number we need swap each path
                count = nums.length / gcd - 1;
                for(int j = 0; j < count; j++){
                    position = (position + step) % nums.length;
                    //swap index value in index i and position
                    nums[i] ^= nums[position];
                    nums[position] ^= nums[i];
                    nums[i] ^= nums[position];
                }
            }
        }
        
        public int findGcd(int a, int b){
            return (a == 0 || b == 0) ? a + b : findGcd(b, a % b);
        }
        
    }
    

    Method 2:( 3 reverse thinking, O(n) time cost, O(1) space cost)

    public class Solution {
        public void rotate(int[] nums, int k) {
            if(nums.length <= 1){
                return;
            }
            //step each time to move
            int step = k % nums.length;
            reverse(nums,0,nums.length - 1);
            reverse(nums,0,step - 1);
            reverse(nums,step,nums.length - 1);
        }
        
        //reverse int array from n to m
        public void reverse(int[] nums, int n, int m){
            while(n < m){
                nums[n] ^= nums[m];
                nums[m] ^= nums[n];
                nums[n] ^= nums[m];
                n++;
                m--;
            }
        }
    }
    

    Method 3:( Normal way, O(n) time cost, O(k % nums.length) space cost)

    public class Solution {
        public void rotate(int[] nums, int k) {
            if(nums.length <= 1){
                return;
            }
            //step each time to move
            int step = k % nums.length;
            int[] tmp = new int[step];
            for(int i = 0; i < step; i++){
                tmp[i] = nums[nums.length - step + i];
            }
            for(int i = nums.length - step - 1; i >= 0; i--){
                nums[i + step] = nums[i];
            }
            for(int i = 0; i < step; i++){
                nums[i] = tmp[i];
            }
            
        }
        
    }

  • 0
    B
    This post is deleted!

  • 0
    B

    Good job, similarly, I implemented the first method and the second method is like a magic, how can it be? :P

    The following is my code using method 1.

    class Solution {
    public:
    int gcd(int a, int b)
    {
    for (;;)
    {
        if (a == 0) return b;
        b %= a;
        if (b == 0) return a;
        a %= b;
    }
    }
    
    int lcm(int a, int b)
    {
     int temp = gcd(a, b);
    
     return temp ? (a / temp * b) : 0;
     }
    
    void rotate(int nums[], int n, int k) 
    {
    int cycnum = 0,t=0, temp = 0, temp1 = 0, c = 1, place = 0, i = 0, j = 0;
    
    if (!n || !(k%n))
    	return;
    k = k%n;
    
    cycnum=lcm(k,n)/k; //steps for each cycle
    c=n/cycnum; //nums of cycles
    while (c--)
    {
    	i = j;
    	t = cycnum;
    	temp = nums[i];
    	while (t--)
    	{
    		place = (i + k) % n;
    		temp1 = nums[place];
    		nums[place] = temp;
    		temp = temp1;
    		i = place;
    	}
    
    	j++;
    }
    }};

  • 0

    Good implementation and very appreciate for your praising! Actually right shift k steps will move right most k elements to the left side. Here is an example of the second method:

    with n = 7 and k = 3, the array [1,2,3,4,5,6,7]

    1. reverse the whole array -> [7,6,5,4,3,2,1]

    2. reverse 1 to k elements -> [5,6,7,4,3,2,1]

    3. reverse k+1 to the end -> [5,6,7,1,2,3,4]


  • 0
    S

    what are count and gcd meant for please elaborate ?


  • 1

    Here use a example input array [1,2,3,4,5,6,7,8] (n = 8) to explain:

    1. suppose k = 3:

    GCD = gcd(3,8) = 1, which means there is only one path.

    Count = (n / GCD) - 1 = 7, which means we need 7 swaps to finish the path. (actually for a path have x element, we need x - 1 swaps)

    Then we can simulate the process of the algorithm,

    path0(each time swap index0 element and indexPosition element):

    [1,2,3,4,5,6,7,8] (position = 3) -> [4,2,3,1,5,6,7,8] (position = 6) -> [7,2,3,1,5,6,4,8](position = 1) -> [2,7,3,1,5,6,4,8](position = 4) -> [5,7,3,1,2,6,4,8](position = 7) -> [8,7,3,1,2,6,4,5](position = 2) -> [3,7,8,1,2,6,4,5](position = 5) -> [6,7,8,1,2,3,4,5] -> finished, total 7 times swap. Final result [6,7,8,1,2,3,4,5]

    1. suppose k = 2:

    Similary, GCD = 2, which means there are 2 paths.

    count = 3, which means we need 3 swaps to finish each path.

    Give the process:

    path0(swap index0 and position element):

    [1,2,3,4,5,6,7,8](position = 2) -> [3,2,1,4,5,6,7,8](position = 4) ->[5,2,1,4,3,6,7,8](position = 6) -> [7,2,1,4,3,6,5,8] -> path0 finished

    Then we continue processing path1(swap index1 and position element):

    [7,2,1,4,3,6,5,8](position = 3) -> [7,4,1,2,3,6,5,8](position = 5) -> [7,6,1,2,3,4,5,8](position = 7) ->[7,8,1,2,3,4,5,6] -> path1 finished -> all path finished we get the result [7,8,1,2,3,4,5,6]


  • 7

    Detail explain of method 1:

    Here use a example input array [1,2,3,4,5,6,7,8] (n = 8) to explain:

    1.suppose k = 3:

    GCD = gcd(3,8) = 1, which means there is only one path.

    Count = (n / GCD) - 1 = 7, which means we need 7 swaps to finish the path. (actually for a path have x element, we need x - 1 swaps)

    Then we can simulate the process of the algorithm,

    path0(each time swap index0 element and indexPosition element):

    [1,2,3,4,5,6,7,8] (position = 3) -> [4,2,3,1,5,6,7,8] (position = 6) -> [7,2,3,1,5,6,4,8](position = 1) -> [2,7,3,1,5,6,4,8](position = 4) -> [5,7,3,1,2,6,4,8](position = 7) -> [8,7,3,1,2,6,4,5](position = 2) -> [3,7,8,1,2,6,4,5](position = 5) -> [6,7,8,1,2,3,4,5] -> finished, total 7 times swap. Final result [6,7,8,1,2,3,4,5]

    2.suppose k = 2:

    Similary, GCD = 2, which means there are 2 paths.

    count = 3, which means we need 3 swaps to finish each path.

    Give the process:

    path0(swap index0 and position element):

    [1,2,3,4,5,6,7,8](position = 2) -> [3,2,1,4,5,6,7,8](position = 4) ->[5,2,1,4,3,6,7,8](position = 6) -> [7,2,1,4,3,6,5,8] -> path0 finished

    Then we continue processing path1(swap index1 and position element):

    [7,2,1,4,3,6,5,8](position = 3) -> [7,4,1,2,3,6,5,8](position = 5) -> [7,6,1,2,3,4,5,8](position = 7) ->[7,8,1,2,3,4,5,6] -> path1 finished -> all path finished we get the result [7,8,1,2,3,4,5,6]


  • 0
    S

    thanks a lot,your explanation is very clear,but what i did not understand in the first place is why are you calculating gcd to find the paths & Count =(n/gcd)-1 to find the steps


  • 0

    I found given a number N and a move steps K. Start from any position P0 of N, keep move right position K by K, the position will back to original one(P0) after N / gcd(N,K) = (count + 1)times.

    In this question every element(N elements) in the array should move right K position. And N = gcd(N,K) * (count + 1), means we can divided N elements into gcd(N,K) differents part(each part has a move path), move every element in each part right K position, then we get the result.


  • 0
    R

    i also do not undanstand,can you explain it?


  • 0

    I have explained it before, you could see comment before you, hope it helpful.


  • 0
    S

    thanks again took me a quite a long time to understand (nearly 2 hours),basic high school math problem


  • 0
    N

    nice solution


  • 0
    W

    public class Solution {
    public void rotate(int[] nums, int k) {
    if(nums.length <= 1){
    return;
    }
    //step each time to move
    int step = k % nums.length;
    int[] tmp = new int[step];
    for(int i = 0; i < step; i++){
    tmp[i] = nums[nums.length - step + i];
    }
    int n = nums.length;
    for(int i = nums.length - step - 1; i >= 0; i--){
    nums[n--] = nums[i];
    }
    for(int i = 0; i < step; i++){
    nums[i] = tmp[i];
    }

    }
    

    }

    find error
    for(int i = nums.length - step - 1; i >= 0; i--){
    nums[n--] = nums[i];
    }

    java.lang.ArrayIndexOutOfBoundsException: 7


  • 2
    L

    Hi, here is another interesting solution different from all of yours. It kind of shares some basic idea with your 1st solution. But I don't compute GCD and count of steps for each path. I just let it jumps from one path to another after finishing the previous path. And I didn't use swap() to process a path. Hope you are interested in it. :)

    //Time complexity O(n), extra space cost O(1)

    public class Solution {
        public void rotate(int[] nums, int k) {
            k %= nums.length;
            if(k<=0) return;
            int index = k, loopHead = 0, curr = nums[0];
            //1. index is the index of the element we will update in each iteration. 
            //2. loopHead is head of a loop (if exist) for index since each time we
            // move index k steps further.
            //3. curr is the value got from previous iteration nums[preIndex] and 
            //for updating nums[index]
            for(int count=0;count<nums.length;count++){
                if(index==loopHead){ //loop detected
                    nums[index] = curr; //set the value of loopHead.
                    loopHead++; //move 1 step further to jump out of loop
                    curr = nums[++index]; //This is the head of new loop
                    index = (index+k)%nums.length;
                }
                else{ //each time go k steps further
                    int tmp = nums[index];
                    nums[index] = curr;
                    curr = tmp;
                    index = (index+k)%nums.length;
                }
            }
        }
    }

  • 0

    Nice!! ........


  • 0
    E

    very nice solutions!


  • 0

    Won't the XOR method for number swap fail for equal numbers?


  • 0

    example: 5 XOR 5 = 0; 5 XOR 0 = 5; 5 XOR 0 = 5;
    It won't fail.


  • 0
    J

    Can anyone please explain why the last step in Method 3 have to be:
    for(int i = 0; i < step; i++){
    nums[i] = tmp[i];
    }
    instead of simply assign tmp to nums by: nums = tmp;


Log in to reply
 

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