Star

Leetcode 189.Rotate Array

Posted on | In |

Question:

Rotate an array of n elements to the right by k steps.

For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

Note: Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.

Hint: Could you do it in-place with O(1) extra space?

Related problem: Reverse Words in a String II

There are three solutions for this problem:

Solution 1:

We can use temporary array to store k elements.

Time complexity: O(N)
Space complexity: O(k), use extra space

Code: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public void rotate(int[] nums, int k) {
    int n= nums.length;
    k = k%n;
    // store the k elements at the end of the array
    int[] temp = new int[k];
    System.arraycopy(nums, n-k, temp, 0, k);
    // rotate the left elements to the end of the array
    for(int i = n-k-1; i>= 0;i--) {
        nums[i+k] = nums[i];
    }
    // put temp elements to the top of the arrray
    for(int i = 0; i< k; i++) {
        nums[i] = temp[i];
    }
}

The solution beat 98% in java submissions.

Solution2:

Reversal, for example: 

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

Time complexity:O(N)
Space complexity:O(1)

Code: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public void rotate(int[] nums, int k) {
    int n = nums.length;
    k = k % n;
    reverse(nums, n-k, n-1);
    reverse(nums, 0, n-k-1);
    reverse(nums, 0, n-1);
}
public void reverse(int[] nums, int start, int end) {
    while(start < end) {
        int temp = nums[start];
        nums[start] = nums[end];
        nums[end] = temp;
        start ++;
        end --;
    }
}

The solution beats 13.19% of java submissions.

Solution3:

Time complexity: O(N)
Space complexity: O(1)

To rotate k steps once for an element. Set all elements to gcd groups.

E.g. nums = [1 2 3 4 5 6], k=2

We use gcd (greatest common divisor) between n and k.
gcd = 2

// count is the number we need swap each path
count = nums.length / gcd - 1 = 2

1st iteration: starts from nums[i=0], keep rotate nums[i+k] until meet the start position

   nums = [\_5 2 \_1 4 \_3 6]

2nd iteration: starts from nums[i=1]

   nums = [5 \_6 1 \_2 3 \_4]

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public void rotate(int[] nums, int k) {
    int n = nums.length;
    if (n <= 1) {
        return ;
    }
     k = k % n;
    int g = gcd(k, n);
    int position, count;
    for(int i= 0; i< g; i++) {
        position = i;
        // count is the number we need swap each path
        count = n/g - 1;
        System.out.println(g);
        System.out.println(count);
        for (int j= 0; j< count; j++) {
            position = (position + k) % nums.length;
            int temp = nums[i];
            nums[i] = nums[position];
            nums[position] = temp;
        }
    }
}
int gcd(int a, int b) {
    if (a == 0 || b == 0 )
        return a + b;
    else
        return gcd(b, a % b);
}
}

References: http://yucoding.blogspot.com/2015/03/leetcode-question-rotate-array.html
http://www.programcreek.com/2015/03/rotate-array-in-java/
P.s. recommend the website: http://www.programcreek.com